本文共 1372 字，大约阅读时间需要 4 分钟。
正解：前缀和+二维差分
差分其实就是前缀和的逆运算；
给你一个数组 a [ 5 ] = 1 ， 2 ， 3 ， 4 ， 5 a[5]={1，2，3， 4，5} a[5]=1，2，3，4，5；差分数组 b [ 5 ] = 1 ， 1 ， 1 ， 1 ， 1 b[5]={1，1，1，1，1} b[5]=1，1，1，1，1；显然差分数组 b [ i ] = a [ i ] − a [ i − 1 ] b[i]=a[i]-a[i-1] b[i]=a[i]−a[i−1];
那么我们可以推出， a [ 1 ] = b [ 1 ] , a [ 2 ] = b [ 1 ] + b [ 2 ] … b [ i ] a[1]=b[1],a[2]=b[1]+b[2]…b[i] a[1]=b[1],a[2]=b[1]+b[2]…b[i]的前缀和等于 a [ i ] a[i] a[i],这也是为什么说差分就是前缀和的逆运算；
知道了这个，差分还有个运用；就是在区间 [ l , r ] [l,r] [l,r]进行加数操作，然后问你某个位置在操作完后的值是多少；
二维差分和一维差分本质上是一样的
就是把 a a a 数组 x 1 , y 1 , x 2 , y 2 x1,y1,x2,y2 x1,y1,x2,y2的四个角赋值为 1 1 1 或 − 1 -1 −1；a[x1][y1]++;a[x2+1][y2+1]++;a[x1][y2+1]--;a[x2+1][y1]--;
这样就能做出来啦！
#include#include #include #include using namespace std;long long f[3500][3500],a[3500][3500]; long long n,m,x,y,x1,y1,x2,y2;int main(){ freopen("square.in","r",stdin); freopen("square.out","w",stdout); scanf("%lld",&n); for(int i=1; i<=n; i++) { scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2); a[x1][y1]++; //差分 a[x2+1][y2+1]++; a[x1][y2+1]--; a[x2+1][y1]--; } for(int i=1; i<=3000; i++) for(int j=1; j<=3000; j++) f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j]; //前缀和 cin>>m; for(int i=1; i<=m; i++) { scanf("%lld %lld",&x,&y); printf("%lld\n",f[x][y]); } return 0;}
转载地址：http://bjle.baihongyu.com/