BZOJ3132: 上帝造题的七分钟

3132: 上帝造题的七分钟

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 483 Solved: 222
[Submit][Status]

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

HINT

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

Source

tyvj

题解：
线段树做不了吧，MLE。。。
然后树状数组：
对于矩阵A，A[i][j]表示[i,j]-[n,m]的增量。那么子矩阵[1,1]-[x,y]的总和为：

代码：

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1000000000
 24 
 25 #define maxn 2050
 26 
 27 #define maxm 500+100
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define mod 1000000007
 44 
 45 using namespace std;
 46 
 47 inline int read()
 48 
 49 {
 50 
 51     int x=0,f=1;char ch=getchar();
 52 
 53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 54 
 55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 56 
 57     return x*f;
 58 
 59 }
 60 int n,m,s[4][maxn][maxn];
 61 inline void add(int z,int x,int y,int t)
 62 {
 63     for(int i=x;i<=n;i+=i&(-i))
 64         for(int j=y;j<=m;j+=j&(-j))
 65             s[z][i][j]+=t;
 66 }
 67 inline int sum(int z,int x,int y)
 68 {
 69     int t=0;
 70     for(int i=x;i;i-=i&(-i))
 71         for(int j=y;j;j-=j&(-j))
 72             t+=s[z][i][j];
 73     return t;
 74 }
 75 inline int getsum(int x,int y)
 76 {
 77     return (x+1)*(y+1)*sum(0,x,y)-(y+1)*sum(1,x,y)-(x+1)*sum(2,x,y)+sum(3,x,y);
 78 }
 79 
 80 int main()
 81 
 82 {
 83 
 84     freopen("input.txt","r",stdin);
 85 
 86     freopen("output.txt","w",stdout);
 87 
 88     n=read();m=read();char ch[2];
 89     while(scanf("%s",ch)!=EOF)
 90     {
 91         if(ch[0]=='L')
 92         {
 93             int x1=read(),y1=read(),x2=read(),y2=read(),z=read();
 94             add(0,x1,y1,z);      add(0,x2+1,y2+1,z);              add(0,x2+1,y1,-z);          add(0,x1,y2+1,-z);
 95             add(1,x1,y1,z*x1);   add(1,x2+1,y2+1,z*(x2+1));       add(1,x2+1,y1,-z*(x2+1));   add(1,x1,y2+1,-z*x1);
 96             add(2,x1,y1,z*y1);   add(2,x2+1,y2+1,z*(y2+1));       add(2,x2+1,y1,-z*y1);       add(2,x1,y2+1,-z*(y2+1));
 97             add(3,x1,y1,z*x1*y1);add(3,x2+1,y2+1,z*(x2+1)*(y2+1));add(3,x2+1,y1,-z*(x2+1)*y1);add(3,x1,y2+1,-z*x1*(y2+1));
 98         }
 99         else
100         {
101             int x1=read(),y1=read(),x2=read(),y2=read();
102             printf("%d
",getsum(x1-1,y1-1)+getsum(x2,y2)-getsum(x2,y1-1)-getsum(x1-1,y2));
103         }
104     }
105 
106     return 0;
107 
108 }

View Code