2 条题解
-
0
// 二维线段树 点修+区查 O(Q*logN*logN) #include <bits/stdc++.h> using namespace std; const int N=1050; #define mid ((l+r)>>1) int n, root, totx, xls[N*2], xrs[N*2]; int toty, rt[N*2], yls[N*2*N*2], yrs[N*2*N*2], d[N*2*N*2]; void changeY(int &p, int l, int r, int y, int c) { if(!p)p=++toty; d[p]+=c; if(l==r) return; if(y<=mid) changeY(yls[p], l, mid, y, c); else changeY(yrs[p], mid+1, r, y, c); } void changeX(int &p, int l, int r, int x, int y, int c) { if(!p)p=++totx; changeY(rt[p], 1, n, y, c); if(l==r) return; if(x<=mid) changeX(xls[p], l, mid, x, y, c); else changeX(xrs[p], mid+1, r, x, y, c); } int queryY(int p, int l, int r, int y1, int y2) { if(!p) return; if(y1<=l&&r<=y2)return d[p]; int res=0; if(y1<=mid) res+=queryY(yls[p], l, mid, y1, y2); if(mid< y2) res+=queryY(yrs[p], mid+1, r, y1, y2); return res; } int queryX(int p, int l, int r, int x1, int x2, int y1, int y2) { if(!p) return; if(x1<=l&&r<=x2)return queryY(rt[p], 1, n, y1, y2); int res=0; if(x1<=mid) res+=queryX(xls[p], l, mid, x1, x2, y1, y2); if(x2> mid) res+=queryX(xrs[p], mid+1, r, x1, x2, y1, y2); return res; } int main() { int op, x, y, c, x1, x2, y1, y2; while(scanf("%d", &op)!=EOF) { if(op==0) { scanf("%d", &n); root=totx=toty=0;memset(d,0,sizeof(d)); // 初始化 } if(op==1) // 点修 { scanf("%d%d%d", &x, &y, &c); x++, y++; // 坐标转换 changeX(root, 1, n, x, y, c); } if(op==2) // 区查 { scanf("%d%d%d%d", &x1, &y1, &x2, &y2);x1++, y1++, x2++, y2++; printf("%d\n", queryX(root, 1, n, x1, x2, y1, y2)); } if(op==3) break; } return 0; }#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=2100; int n, m, op; LL c1[N][N], c2[N][N], c3[N][N], c4[N][N]; // 4个二维树状数组 // 二维树状数组差分更新 void add(int x, int y, LL z) { for(int i=x;i<=n;i+=i&-i) for(int j=y;j<=m;j+=j&-j) { c1[i][j] += z; c2[i][j] += z*x; c3[i][j] += z*y; c4[i][j] += z*x*y; } } // 二维前缀和查询 (x,y)为右上角的矩形和 LL sum(int x, int y) { LL sum=0; for(int i=x;i>=1;i-=i&-i) for(int j=y;j>=1;j-=j&-j) sum += c1[i][j]*(x+1)*(y+1) - c2[i][j]*(y+1) - c3[i][j]*(x+1) + c4[i][j]; return sum; } int main() { scanf("%d%d", &n, &m); while(scanf("%d", &op)!=EOF) { int x, y, a, b; LL z; scanf("%d%d%d%d", &a, &b, &x, &y); if(op==1) { // 更新矩形(a,b)-(x,y) scanf("%lld", &z); add(a, b, z); add(x+1, y+1, z); add(a, y+1, -z); add(x+1, b, -z); } else { // 查询矩形(a,b)-(x,y)的和 printf("%lld\n", sum(x, y)-sum(x, b-1)-sum(a-1, y)+sum(a-1, b-1)); } } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:07:36
// 二维线段树 点修+区查 O(QlogNlogN) #include<bits/stdc++.h> using namespace std; const int N=1050; #define mid ((l+r)>>1) int n,root,totx,xls[N2],xrs[N2]; int toty,rt[N2],yls[N2N2],yrs[N2N2],d[N2N2]; void changeY(int &p,int l,int r,int y,int c) { if(!p)p=++toty; d[p]+=c; if(lr) return; if(y<=mid) changeY(yls[p],l,mid,y,c); else changeY(yrs[p],mid+1,r,y,c); } void changeX(int &p,int l,int r,int x,int y,int c) { if(!p)p=++totx; changeY(rt[p],1,n,y,c); if(lr) return; if(x<=mid) changeX(xls[p],l,mid,x,y,c); else changeX(xrs[p],mid+1,r,x,y,c); } int queryY(int p,int l,int r,int y1,int y2) { if(!p) return 0; if(y1<=l&&r<=y2)return d[p]; int res=0; if(y1<=mid) res+=queryY(yls[p],l,mid,y1,y2); if(mid< y2) res+=queryY(yrs[p],mid+1,r,y1,y2); return res; } int queryX(int p,int l,int r,int x1,int x2,int y1,int y2) { if(!p) return 0; if(x1<=l&&r<=x2)return queryY(rt[p],1,n,y1,y2); int res=0; if(x1<=mid) res+=queryX(xls[p],l ,mid,x1,x2,y1,y2); if(x2> mid) res+=queryX(xrs[p],mid+1,r,x1,x2,y1,y2); return res; } int main() { int op,x,y,c,x1,x2,y1,y2; while(scanf("%d",&op)!=EOF) { if(op0) { scanf("%d",&n); root=totx=toty=0;memset(d,0,sizeof(d)); } if(op1) { scanf("%d%d%d",&x,&y,&c); x++,y++; changeX(root,1,n,x,y,c); } if(op2) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2);x1++,y1++,x2++,y2++; printf("%d\n",queryX(root,1,n,x1,x2,y1,y2)); } if(op3) break; } return 0; }
C94 二维树状数组+差分 P4514 上帝造题的七分钟#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=2100; int n, m, op; LL c1[N][N], c2[N][N], c3[N][N], c4[N][N]; void add(int x, int y, LL z) {
for(int i=x;i<=n;i+=i&-i) for(int j=y;j<=m;j+=j&-j) { c1[i][j]+=z; c2[i][j]+=zx; c3[i][j]+=zy; c4[i][j]+=zxy; } } LL sum(int x, int y) { LL sum=0; for(int i=x;i>=1;i-=i&-i) for(int j=y;j>=1;j-=j&-j) sum+=c1[i][j](x+1)(y+1)-c2[i][j](y+1)-c3[i][j](x+1)+c4[i][j]; return sum; } int main() { scanf("%d%d", &n, &m); while(scanf("%d", &op)!=EOF) { int x, y, a, b; LL z; scanf("%d%d%d%d", &a, &b, &x, &y); if(op==1) { scanf("%lld", &z); add(a, b, z); add(x+1, y+1, z); add(a, y+1, -z); add(x+1, b, -z); } else printf("%lld\n", sum(x, y)-sum(x, b-1)-sum(a-1, y)+sum(a-1, b-1)); } return 0; }
- 1
