oj-进阶

极大子矩阵、单调栈、单调队列、前缀和、差分、离散化

极大子矩阵

悬线法

P4147 玉蟾宫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
#define INT_MAX 2147483647
int a[1010][1010];
int r[1010][1010];
int l[1010][1010];
int up[1010][1010];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,m;
	cin>>n>>m;
	int ans=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			{
				char c;
				cin>>c;
				if(c=='F')	a[i][j]=1,up[i][j]=1;
			}
	for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				r[i][j]=l[i][j]=j;
	for(int i=0;i<n;i++)
			for(int j=m-2;j>=0;j--)
				if(a[i][j]&&a[i][j+1]) r[i][j]=r[i][j+1];
	for(int i=0;i<n;i++)
			for(int j=1;j<m;j++)
				if(a[i][j]&&a[i][j-1]) l[i][j]=l[i][j-1];
	for(int i=1;i<n;i++)
			for(int j=0;j<m;j++)
			{	if(a[i][j]&&a[i-1][j])
					r[i][j]=min(r[i][j],r[i-1][j]),
					l[i][j]=max(l[i][j],l[i-1][j]),
					up[i][j]=up[i-1][j]+1;
				ans=max(ans,3*(r[i][j]-l[i][j]+1)*up[i][j]);
			}
	cout<<ans;	
	
	return 0;
}

障碍点子矩形

P1578 奶牛浴场

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
#define INT_MAX 2147483647
struct point
{
	int x;
	int y;
}p[5010];


bool cmp1(point a,point b)
{	return a.x<b.x; }
bool cmp2(point a,point b)
{	return a.y<b.y; }
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int L,W;
	cin>>L>>W;
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>p[i].x>>p[i].y;
	p[n++].x=0,p[n].y=0;
	p[n++].x=0,p[n].y=W;
	p[n++].x=L,p[n].y=0;
	p[n++].x=L,p[n].y=W;
	sort(p,p+n,cmp1);
	int ans=0;
	int x1,x2,y1=0,y2=W;
	for(int i=0;i<n;i++)
	{	x1=p[i].x;y1=0,y2=W;
		for(int j=i+1;j<n;j++)
		{
			x2=p[j].x;
			ans=max(ans,(x2-x1)*(y2-y1));
			if(p[j].y>=p[i].y)
				y2=min(y2,p[j].y);
			else 
				y1=max(y1,p[j].y);
		}
	}
	for(int i=n-1;i>=0;i--)
	{	x1=p[i].x;y1=0,y2=W;
		for(int j=i-1;j>=0;j--)
		{
			x2=p[j].x;
			ans=max(ans,(x1-x2)*(y2-y1));
			if(p[j].y>=p[i].y)
				y2=min(y2,p[j].y);
			else 
				y1=max(y1,p[j].y);
		}
	}
	sort(p,p+n,cmp2);
	for(int i=0;i<n-1;i++)
	{
		ans=max(ans,L*(p[i+1].y-p[i].y));
	}
	cout<<ans;
	return 0;
}

单调栈

栈内元素保持单调性（递增或递减）,用于解决”下一个更大/更小元素”类问题,O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 单调递减栈模板（找下一个更大元素）
vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);  // 初始化结果为-1
    stack<int> stk;          // 存储的是索引
    
    for (int i = 0; i < n; ++i) {
        // 当前元素比栈顶元素大时，弹出栈顶并记录结果
        while (!stk.empty() && nums[i] > nums[stk.top()]) {
            res[stk.top()] = nums[i];
            stk.pop();
        }
        stk.push(i);  // 将当前索引入栈
    }
    
    return res;
}

单调队列

单调队列是一种特殊的双端队列，它能够在O(1)时间内获取当前窗口的最大值或最小值，非常适合解决滑动窗口类问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 单调递减队列模板（获取滑动窗口最大值）
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;  // 存储的是索引
    vector<int> res;
    
    for (int i = 0; i < nums.size(); ++i) {
        // 移除超出窗口范围的元素
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }
        
        // 维护单调递减性
        while (!dq.empty() && nums[i] >= nums[dq.back()]) {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        // 当窗口形成时记录结果
        if (i >= k - 1) {
            res.push_back(nums[dq.front()]);
        }
    }
    
    return res;
}

前缀和

利用前缀和可以在常数时间 复杂度中查询区间和
P8218 求区间和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
#define INT_MAX 2147483647
int a[100010];
int sum[100010];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,m;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int l,r;
		cin>>l>>r;
		cout<<sum[r]-sum[l]+a[l]<<endl;
	}
	return 0;
}

差分

利用差分在常数时间复杂度对序列进行区间操作
P2367 语文成绩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
#define INT_MAX 2147483647
int a[5000010];
int d[5000010];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,p;
	cin>>n>>p;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		d[i]=a[i]-a[i-1];
	}
	for(int i=1;i<=p;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		d[x]=d[x]+z;
		d[y+1]=d[y+1]-z;
	}
	int ans=INT_MAX;
	for(int i=1;i<=n;i++)
	{
		a[i]=a[i-1]+d[i];
		ans=min(ans,a[i]);
	}
	cout<<ans;

	
	return 0;
}

P4552 IncDec Sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
#define INT_MAX 2147483647
long long int a[100010];
long long int d[100010];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n;
	long long int sumx=0,sumy=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		d[i]=a[i]-a[i-1];
		if(i>1)
		{
			if(d[i]>0)	sumx+=d[i];
			else if(d[i]<0) sumy-=d[i];
		}
	}
	cout<<max(sumx,sumy)<<endl;
	cout<<abs(sumx-sumy)+1;
	return 0;
}

离散化

利用离散化去除无 用数据区间，通过放缩保留有用的数据

author: YaoGuangMing 2025

转载请标明出处！