首页 > 代码库 > BZOJ3132: 上帝造题的七分钟
BZOJ3132: 上帝造题的七分钟
3132: 上帝造题的七分钟
Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 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
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 ≤ abs(delta) ≤ 500,操作不超过200000个,保证运算过程中及最终结果均不超过32位带符号整数类型的表示范围。
Source
tyvj
题解：
线段树做不了吧，MLE。。。
然后树状数组：
对于矩阵A，A[i][j]表示[i,j]-[n,m]的增量。那么子矩阵[1,1]-[x,y]的总和为：
View Code
线段树做不了吧，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 else100 {101 int x1=read(),y1=read(),x2=read(),y2=read();102 printf("%d\n",getsum(x1-1,y1-1)+getsum(x2,y2)-getsum(x2,y1-1)-getsum(x1-1,y2));103 }104 }105 106 return 0;107 108 }
BZOJ3132: 上帝造题的七分钟
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。