二维树状数组

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define pf printf
 4 #define mem(a,b) memset(a,b,sizeof(a))
 5 #define scand(x) scanf("%llf",&x) 
 6 #define f(i,a,b) for(int i=a;i<=b;i++)
 7 #define scan(a) scanf("%d",&a)
 8 #define dbg(args) cout<<#args<<":"<<args<<endl;
 9 #define pb(i) push_back(i)
10 #define ppb(x) pop_back(x)
11 #define inf 0x3f3f3f3f
12 #define maxn 1010
13 #define ll long long
14 int n,m,t;
15 ll c[maxn<<1][maxn<<1];
16 int lowbit(int x){
17     return x&(-x);
18 }
19 void update(int x,int y,ll C){
20     while(x<maxn){
21         int tmp=y;
22         while(tmp<maxn){
23             c[x][tmp]+=C;
24             tmp+=lowbit(tmp);
25         }
26         x+=lowbit(x);
27     }
28 }
29 ll query(int x,int y){
30     ll ans=0;
31     while(x>0){
32         int tmp=y;
33         while(tmp>0){
34             ans+=c[x][tmp];
35             tmp-=lowbit(tmp);
36         }
37         x-=lowbit(x);
38     }
39     return ans;
40 }
41 ll query2(int l1,int r1,int l2,int r2){
42     return query(l2,r2)-query(l1-1,r2)-query(l2,r1-1)+query(l1-1,r1-1);
43 }
44 
45 int main(){
46     ios::sync_with_stdio(false);
47     scan(t);
48     f(kk,1,t){
49         f(i,1,1001){
50             f(j,1,1001){
51                 c[i][j]=lowbit(i)*lowbit(j);//设置原数组每一个元素都是1，用update(i,j,1)用O(n*log(n)^2)时间会超时 
52             }
53         }
54         scan(n);
55         //cout<<"n is: "<<n<<endl;
56         int xa,xb,ya,yb;
57         ll n1;
58         pf("Case %d:\n",kk);
59         while(n--){
60             char s;
61             getchar();
62             scanf("%c",&s);
63             //cout<<"s is: "<<s<<endl;
64             if(s==‘S‘){
65                 scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
66                 xa++,xb++,ya++,yb++;
67                 if(xa>xb) swap(xa,xb);
68                 if(ya>yb) swap(ya,yb);
69                 pf("%lld\n",query2(xa,ya,xb,yb));
70                 //cout<<"query successful!\n";
71             }
72             else if(s==‘A‘){
73                 scanf("%d%d%lld",&xa,&ya,&n1);
74                 update(xa+1,ya+1,n1);
75                 //cout<<"update point successful!\n";
76             }
77             else if(s==‘D‘){
78                 scanf("%d%d%lld",&xa,&ya,&n1);
79                 xa++,ya++;
80                 ll tmp=query2(xa,ya,xa,ya);
81                 n1=min(n1,tmp);
82                 update(xa,ya,-n1);
83             }
84             else if(s==‘M‘){
85                 scanf("%d%d%d%d%lld",&xa,&ya,&xb,&yb,&n1);
86                 xa++,ya++,xb++,yb++;
87                 ll tmp=query2(xa,ya,xa,ya);
88                 n1=min(n1,tmp);
89                 update(xa,ya,-n1);
90                 update(xb,yb,n1);
91             }
92             //cout<<"now n is: "<<n<<endl; 
93         }
94     }
95  }