CodeForces - 707E Garlands (二维树状数组)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef double db;
 5 const int N=2000+10,inf=0x3f3f3f3f;
 6 int n,m,k,Q,nqr,state[N];
 7 char buf[N];
 8 ll c[N][N],ans[N];
 9 int lb(int x) {return x&-x;}
10 void add(int u,int v,int x) {
11     for(int i=u; i<=n; i+=lb(i))
12         for(int j=v; j<=m; j+=lb(j))c[i][j]+=x;
13 }
14 ll get(int u,int v) {
15     ll ret=0;
16     for(int i=u; i; i-=lb(i))
17         for(int j=v; j; j-=lb(j))ret+=c[i][j];
18     return ret;
19 }
20 struct P {int x,y,c;};
21 vector<P> vec[N];
22 struct Q {int x1,y1,x2,y2;} qr[N];
23 vector<int> gx[N];
24 
25 int main() {
26     scanf("%d%d%d",&n,&m,&k);
27     for(int i=1; i<=k; ++i) {
28         int l;
29         scanf("%d",&l);
30         while(l--) {
31             int x,y,c;
32             scanf("%d%d%d",&x,&y,&c);
33             vec[i].push_back({x,y,c});
34         }
35     }
36     for(int i=1; i<=k; ++i)state[i]=1;
37     for(scanf("%d",&Q); Q--;) {
38         int x1,x2,y1,y2,u;
39         scanf("%s",buf);
40         if(buf[0]==‘S‘)scanf("%d",&u),state[u]^=1;
41         else {
42             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
43             qr[++nqr]= {x1,y1,x2,y2};
44             for(int i=1; i<=k; ++i)if(state[i])gx[i].push_back(nqr);
45         }
46     }
47     for(int i=1; i<=k; ++i) {
48         for(P p:vec[i])add(p.x,p.y,p.c);
49         for(int x:gx[i]) {
50             int x1=qr[x].x1,y1=qr[x].y1,x2=qr[x].x2,y2=qr[x].y2;
51             ans[x]+=get(x2,y2)-get(x1-1,y2)-get(x2,y1-1)+get(x1-1,y1-1);
52         }
53         for(P p:vec[i])add(p.x,p.y,-p.c);
54     }
55     for(int i=1; i<=nqr; ++i)printf("%lld\n",ans[i]);
56     return 0;
57 }