BZOJ 3132(上帝造题的七分钟-树状数组求和+2D逆求和数组)

3132: 上帝造题的七分钟

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 46  Solved: 18
[Submit][Status][Discuss]

Description

“第一分钟,X说,要有矩阵,于是便有了一个里面写满了0的n×m矩阵。

第二分钟,L说,要能修改,于是便有了将左上角为(a,b),右下角为(c,d)的一个矩形区域内的全部数字加上一个值的操作。

第三分钟,k说,要能查询,于是便有了求给定矩形区域内的全部数字和的操作。

第四分钟,彩虹喵说,要基于二叉树的数据结构,于是便有了数据范围。

第五分钟,和雪说,要有耐心,于是便有了时间限制。

第六分钟,吃钢琴男说,要省点事,于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。

第七分钟,这道题终于造完了,然而,造题的神牛们再也不想写这道题的程序了。”

       ——《上帝造裸题的七分钟》

所以这个神圣的任务就交给你了。

Input

 输入数据的第一行为X n m,代表矩阵大小为n×m。

从输入数据的第二行开始到文件尾的每一行会出现以下两种操作:

  L a b c d delta —— 代表将(a,b),(c,d)为顶点的矩形区域内的所有数字加上delta。

  k a b c d   —— 代表求(a,b),(c,d)为顶点的矩形区域内所有数字的和。

 

请注意,k为小写。


        

Output

针对每个k操作,在单独的一行输出答案。

Sample Input

X 4 4

L 1 1 3 3 2

L 2 2 4 4 1

k 2 2 3 3

Sample Output

12

HINT

对于100%的数据,1 ≤ n ≤ 2048, 1 ≤ m ≤ 2048, 1 ≤ delta ≤ 500,操作不超过200000个,保证运算过程中及最终结果均不超过32位带符号整数类型的表示范围。

Source

2D树状数组支持单点修改+求和(1,1)-(x,y)矩形

因此按照zkw的思路用逆求和数组做(就是把区间修改结构-用2个单点修改的逆求和数组d’,{i*d’}代替,神思路)

#include<cstdio>

include<cstdlib>

include<cstring>

include<iostream>

include<algorithm>

include<functional>

using namespace std;

define MAXN (2050)

int lowbit(int x){return x&(-x);} int n,m,x1,x2,y1,y2,delta; struct arr_tree { int b[MAXN][MAXN]; arr_tree(){memset(b,0,sizeof(b)); } void add(int x,int y,int c,bool b1,bool b2) { if (!x||!y||x>n||y>m) return; if (b1) c=(x-1);if (b2) c=(y-1);if (!c) return; for (int i=x;i<=n;i+=lowbit(i)) for (int j=y;j<=m;j+=lowbit(j)) b[i][j]+=c;
} int qur(int x,int y) { if (!x||!y) return 0; int ans=0; for (int i=x;i;i-=lowbit(i)) for (int j=y;j;j-=lowbit(j)) ans+=b[i][j]; return ans; } void add(int x1,int y1,int x2,int y2,int c,bool b1,bool b2) { add(x2+1,y2+1,delta,b1,b2),add(x1,y1,delta,b1,b2); add(x1,y2+1,-delta,b1,b2),add(x2+1,y1,-delta,b1,b2);
} }d,di,dj,dij; int Dsum(int x,int y) { return d.qur(x,y)xy+dij.qur(x,y)-di.qur(x,y)y-dj.qur(x,y)x; } int main() { scanf("X %d %d",&n,&m); char c; while (scanf("%c",&c)==1) { while (c^'L'&&c^'k') if (scanf("%c",&c)!=1) return 0; switch(c) { case 'L': scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&delta); if (x1>x2) swap(x1,x2),swap(y1,y2); d.add(x1,y1,x2,y2,delta,0,0),di.add(x1,y1,x2,y2,-delta,1,0); dj.add(x1,y1,x2,y2,-delta,0,1),dij.add(x1,y1,x2,y2,delta,1,1); break; default: scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if (x1>x2) swap(x1,x2),swap(y1,y2); printf("%d\n",Dsum(x2,y2)+Dsum(x1-1,y1-1)-Dsum(x1-1,y2)-Dsum(x2,y1-1)); } } }