本文共 1974 字，大约阅读时间需要 6 分钟。
详细解释见小结。
#include #include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:1024000000");#define EPS (1e-8)#define LL long long#define ULL unsigned long long#define _LL __int64#define _INF 0x3f3f3f3f#define Mod 9999991#define lowbit(x) (x&(-x))using namespace std;const int N = 2049;int a[N][N];int ax[N][N];int ay[N][N];int axy[N][N];void Updata(int a[N][N],int x,int y,int n,int m,int data){ for(; x <= n; x += lowbit(x)) { for(int t = y; t <= m; t += lowbit(t)) { a[x][t] += data; } }}int Query(int a[N][N],int x,int y){ int sum = 0; while(x > 0) { for(int t = y; t > 0; t -= lowbit(t)) { sum += a[x][t]; } x -= lowbit(x); } return sum;}int sum(int x,int y){ return Query(a,x,y)*(x+1)*(y+1) - (y+1)*Query(ax,x,y) - (x+1)*Query(ay,x,y) + Query(axy,x,y);}void Add(int x1,int y1,int x2,int y2,int n,int m,int data){ Updata(a,x1,y1,n,m,data); Updata(a,x2+1,y1,n,m,-data); Updata(a,x1,y2+1,n,m,-data); Updata(a,x2+1,y2+1,n,m,data); Updata(ax,x1,y1,n,m,x1*data); Updata(ax,x2+1,y1,n,m,-(x2+1)*data); Updata(ax,x1,y2+1,n,m,-x1*data); Updata(ax,x2+1,y2+1,n,m,(x2+1)*data); Updata(ay,x1,y1,n,m,y1*data); Updata(ay,x2+1,y1,n,m,-y1*data); Updata(ay,x1,y2+1,n,m,-(y2+1)*data); Updata(ay,x2+1,y2+1,n,m,(y2+1)*data); Updata(axy,x1,y1,n,m,x1*y1*data); Updata(axy,x2+1,y1,n,m,-(x2+1)*y1*data); Updata(axy,x1,y2+1,n,m,-x1*(y2+1)*data); Updata(axy,x2+1,y2+1,n,m,(x2+1)*(y2+1)*data);}int main(){ int n,m; char order[10]; int x1,x2,y1,y2,data; memset(a,0,sizeof(a)); memset(ax,0,sizeof(ax)); memset(ay,0,sizeof(ay)); memset(axy,0,sizeof(axy)); while(scanf("%s",order) != EOF) { if(order[0] == 'L') { scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&data); Add(x1,y1,x2,y2,n,m,data); } else if(order[0] == 'k') { scanf("%d %d %d %d",&x1,&y1,&x2,&y2); printf("%d\n",sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1) + sum(x1-1,y1-1)); } else { scanf("%d %d",&n,&m); } } return 0;}
转载地址：http://kyalo.baihongyu.com/