目录
题意：
给出你一个n*m矩阵，矩阵中有一些灯泡，这些灯泡连成了k条互不重叠的链。每个灯泡都有一定的权值w，但是只有当灯泡打开的时候，才会产生贡献，刚开始所有的灯泡都是开着的。共有q次询问，有两种操作：
①\(Switch\) \(i\)——表示将编号为i的链所有的灯泡取反（即开变关，关变开）。 ②\(Ask\) \(x1,y1,x2,y2\)——表示询问以\(（x1,y1）\)和\(（x2,y2）\)为两个端点的子矩形所产生的贡献。数据范围：\(1 ≤ n, m, k ≤ 2000\)，\(1≤w≤ 10^9\)，\(q≤10^6\)，保证\(Ask\)的操作\(≤2000\)次
时限：\(3s\)解题过程：
备注：翻阅了很多的题解，发现大多数的题解都是在线做的，虽然能够过CF的评测，但是其实复杂度可以被卡到\(n^3*log(n)^2\)，自测数据很容易就可以卡掉。所以这里介绍一种不会被卡的离线方法，复杂度为\(n^2*log(n)^2\)的，本机测验极限数据能够跑在3s之内。
下面进入正题。首先我们可以注意到题目中说到了Ask的次数不会超过两千次，于是我们就可以从这里入手。有点类似与线段树\(lazy\)标记，我们可以对于每个\(Switch\)操作，我们并不一定每次都要改，而是进行记录。因为我们可以发现，取反操作对于每个链做了偶数次之后，就相当于没有做，所以我们只需要在每次\(Ask\)的时候，对所需要修改的链进行修改即可。然后我们考虑如何统计答案，既然询问的是子矩阵的贡献和，我们自然会想到前缀和，但是这个子矩阵中包含着不同编号的链，而每条链在每次查询的时候开关的状态是不一样的，所以我们就可以记\(ans\)数组，\(ans[i][j]\)表示假设第i条链是开着的时候，对于第\(j\)个询问的贡献是多少，这个地方就可以用二维树状数组进行维护，预处理的复杂度为\(n^2*log(n)^2\)。最后我们在遍历每一个询问，记\(change\)数组，\(change[i]\)表示第i条链是否要进行修改，\(Ask\)的时候将开着的链贡献添加进去，即为答案，总的复杂度为\(n^2*log(n)^2\)，只要常数不是非常的大，就是很容易过去的。
AC代码：
#includeusing namespace std;typedef long long ll;bool Finish_read;template inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}template inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}template inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}template inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}/*================Header Template==============*/const int maxn=2005;int n,m,k,qcnt,q;ll T[maxn+50][maxn+50];int len[maxn];int x[maxn][maxn],y[maxn][maxn],w[maxn][maxn];int c[1000005],qx1[maxn],qy1[maxn],qx2[maxn],qy2[maxn];bool change[maxn];ll ans[maxn][maxn];#define lowbit(x) x&(-x)/*==================Define Area================*/void Add(int x,int y,int w) { for(int i=x;i<=maxn;i+=lowbit(i)) { for(int j=y;j<=maxn;j+=lowbit(j)) { T[i][j]+=w; } }}ll Sum(int x,int y) { ll res=0; for(int i=x;i;i-=lowbit(i)) { for(int j=y;j;j-=lowbit(j)) { res+=T[i][j]; } } return res;}int main() { read(n);read(m);read(k); for(int i=1;i<=k;i++) { read(len[i]); for(int j=1;j<=len[i];j++) { read(x[i][j]);read(y[i][j]);read(w[i][j]); } } read(q); for(int i=1;i<=q;i++) { char opt[2]; scanf("%s",opt); if(opt[0]=='A') { ++qcnt; read(qx1[qcnt]);read(qy1[qcnt]);read(qx2[qcnt]);read(qy2[qcnt]); } else { read(c[i]); } } for(int i=1;i<=k;i++) { for(int j=1;j<=len[i];j++) { Add(x[i][j],y[i][j],w[i][j]); } for(int j=1;j<=qcnt;j++) { ans[i][j]=Sum(qx2[j],qy2[j])+Sum(qx1[j]-1,qy1[j]-1)-Sum(qx1[j]-1,qy2[j])-Sum(qx2[j],qy1[j]-1); } for(int j=1;j<=len[i];j++) { Add(x[i][j],y[i][j],-w[i][j]); } } for(int i=1,cnt=1;i<=q;i++) { if(c[i]) { change[c[i]]^=1; } else { ll res=0; for(int j=1;j<=k;j++) { if(!change[j]) res+=ans[j][cnt]; } printf("%lld\n",res); cnt++; } } return 0;}