bk老师高中就开始出神题啦，然而蒟蒻如我才刚刚学会二维树状数组QAQ（南瓜什么的真是太菜啦！！呜呜呜
题目描述
“第一分钟，X说，要有矩阵，于是便有了一个里面写满了 00 的 n×mn×m 矩阵。
第二分钟，L说，要能修改，于是便有了将左上角为 (a,b)(a,b) ，右下角为 (c,d)(c,d) 的一个矩形区域内的全部数字加上一个值的操作。 第三分钟，k说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。 第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。 第五分钟，和雪说，要有耐心，于是便有了时间限制。 第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。 第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。” ——《上帝造裸题的七分钟》 所以这个神圣的任务就交给你了。输入输出格式
输入格式：
输入数据的第一行为X n m，代表矩阵大小为 n×mn×m 。
L a b c d delta—— 代表将 (a,b),(c,d)(a,b),(c,d) 为顶点的矩形区域内的所有数字加上delta。k a b c d—— 代表求 (a,b),(c,d)(a,b),(c,d) 为顶点的矩形区域内所有数字的和。
请注意， kk 为小写。
输出格式：
针对每个k操作，在单独的一行输出答案。
输入输出样例
输入样例#1： 复制
X 4 4L 1 1 3 3 2L 2 2 4 4 1k 2 2 3 3
输出样例#1： 复制
12
说明
对于10%的数据， 1 ≤ n ≤ 16, 1 ≤ m ≤ 161≤n≤16,1≤m≤16 , 操作不超过200个.
对于60%的数据， 1 ≤ n ≤ 512, 1 ≤ m ≤ 5121≤n≤512,1≤m≤512 . 对于100%的数据， 1 ≤ n ≤ 2048, 1 ≤ m ≤ 2048, -500 ≤ delta ≤ 5001≤n≤2048,1≤m≤2048,−500≤delta≤500 ,操作不超过200000个,保证运算过程中及最终结果均不超过32位带符号整数类型的表示范围。 by XLk
修改操作
对于区间修改操作，和一维树状数组一样我们采用差分的方法在O（1）的复杂度来修改区间的边界就行啦（一维树状数组差分参考luogu P3368 树状数组2）
和一维树状数组不同的是二维树状数组修改的是四个区间边界点
如下矩阵:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
当我们想给中间那个2*3的矩阵加上x时，差分数组的变化应该是：
0 0 0 0 0 0 +x 0 0 -x 0 0 0 0 0 0 -x 0 0 +x
这种修改操作是很明显正确的，只会对修改区间内的值进行修改，可以类比一维树状数组感性的理解一下下qvq
查询操作
对于查询一个点（x，y）我们的操作是对差分数组从（1,1）到（x，y）进行求和就完啦。但我们惊讶的发现这bt的神学题居然是求区间和QAQ！！
对于实现区间修改和区间求和的操作我们一般会选用线段树来维护，但对于二维的区间操作，二维线段树的实现较难而且会炸空间和时间，所以我们不选择二维线段树（听说上一个码二维线段树的dalao已经疯了qwq
然后我们怎么在保证时间和空间复杂度的情况下来解决这丧心病狂的毒瘤查询呢qwq
由于南瓜实在是太弱啦！！不仅推不出式子还打不来求和符号qwq（只能勉强感性的理解一下），就只能copy大佬的题解啦QAQ（摘自luogu，权侵删）
然后我们维护四个树状数组，分别记录d[i][j]，d[i][j]*i,d[i][j]*j,d[i][j]*i*j;然后在查询的时候分别乘上系数(xy+x+y+1),-(y+1),-(x+1),1就好啦ww
以下是南瓜的辣鸡代码qvq
#include#include #include #define maxn 2048+10using namespace std;char op[3];int n,m,x1,y1,x2,y2,w;int read(){ int xx=0,kk=1;char ch=' '; while(ch<'0'||ch>'9'){ch=getchar();if(ch=='-')kk=-1;} while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();} return kk*xx;}struct qwq{ int c[maxn][maxn]; inline int lowbit(int x){ return x&-x;} inline void add(int x,int y,int w) { for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=m;j+=lowbit(j)) c[i][j]+=w; } int query(int x,int y) { int ans=0; for(int i=x;i>=1;i-=lowbit(i)) for(int j=y;j>=1;j-=lowbit(j)) ans+=c[i][j]; return ans; }}a1,a2,a3,a4;void Add(int x,int y,int w){ a1.add(x,y,w);a2.add(x,y,w*x); a3.add(x,y,w*y);a4.add(x,y,w*x*y);}int Query(int x,int y){ return a1.query(x,y)*(x*y+x+y+1)-a2.query(x,y)*(y+1)-a3.query(x,y)*(x+1)+a4.query(x,y);}int main(){ scanf("X %d %d",&n,&m); while(~scanf("%s",&op)) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(op[0]=='L') { w=read(); Add(x1,y1,w),Add(x2+1,y2+1,w); Add(x1,y2+1,-w),Add(x2+1,y1,-w); } else printf("%d\n",Query(x2,y2)+Query(x1-1,y1-1)-Query(x1-1,y2)-Query(x2,y1-1)); } return 0;}
后排提醒，数据会卡读优！！
O(n^2logn)的时间复杂度，常数也有点点大，比大佬们优秀的代码跑的慢多啦QAQ，还要继续努力呢
(´°̥̥̥̥̥̥̥̥ω°̥̥̥̥̥̥̥̥｀)