前缀和
https://www.luogu.com.cn/problem/P2280
一维前缀和
维护一个前缀和数组，使得每一个元素num[i]等于从a[1]到a[i]所有元素之和，一位前缀和非常好写。
这个时候如果我们要求某一区间[l,r]中所有元素的和，只需要用num[r]-num[l-1]即可
二维前缀和
我们用num[i][j]表示从(1,1)到(i,j)，a数组的所有元素的和，这个如何操作呢，我们可以想象成求面积
我们需要求的是一个蓝色正方形的面积，蓝色正方形的面积就等于绿色加紫色，去掉重复部分的一个红色，最后加上没有加的这个元素
也就是num[i][j]=num[i-1][j]+num[i][j-1]-num[i-1][j-1]+a[i][j];
那么如果我的边长是定值m，如何求一个正方形的面积呢
比如我们要求一个绿色矩形的面积，我们还是采用割补的想法，绿色矩形的面积等于蓝色矩形减掉黄色矩形减掉紫色矩形，最后加回去一个重复的红色矩形部分
也就是ans = sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]
那么再看回这道题，这道题其实就是先构造一个二维前缀和数组，然后枚举点(x2,y2)，找出最大值即可
#include <bits/stdc++.h>
using namespace std;
int a[9001][9001];
int n;
int m;
int b[9001][9001];
int main () {
scanf("%d %d" ,&n,&m);
for(int i = 1;i <= n; i++) {
int x,y,z;
scanf("%d %d %d" ,&x,&y,&z);
a[x + 1][y + 1] += z;
}
for(int i = 1;i <= 5005; i++) {
for(int j = 1;j <= 5005; j++) {
b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];
}
}
int num = 0;
for(int i = m; i <= 5005; i++) {
for(int j = m;j <= 5005; j++) {
num = max(num,b[i][j] - b[i - m][j] - b[i][j - m] + b[i - m][j - m]);
}
}
printf("%d" ,num);
return 0;
}
双指针
https://www.luogu.com.cn/problem/CF1793C
其实双指针与其说是算法，不如说是一种解决问题的想法和技巧
例如这道题，首先最重要的一点是他给出了一个1n的排列，因此1n一定是包含在这个序列里的
其次，就是，在区间大小不断减小的过程中，其最大值一定单调不升，最小值一定单调不降，所以每次我们只需要分别检查两个端点，不符合条件的话就缩短空间即可
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1000001] = { };
int l,r;
int mi,ma;
int t;
int main () {
scanf("%d" ,&t);
while(t--) {
scanf("%d" ,&n);
l = 1;
r = n;
for(int i = 1;i <= n; i++) {
scanf("%d" ,&a[i]);
}
mi = 1;
ma = n;
while(l <= r) {
if(a[l] == ma) {
l++;
ma--;
continue;
}
else if(a[l] == mi) {
l++;
mi++;
continue;
}
else if(a[r] == ma) {
r--;
ma--;
continue;
}
else if(a[r] == mi) {
r--;
mi++;
continue;
} else break;
}
if(l > r) printf("-1\n");
else printf("%d %d\n" ,l,r);
//memset(a,0,sizeof(a));
}
}