tyvj P1716

P1716 - 上帝造题的七分钟

From Riatre    Normal (OI)
总时限：50s    内存限制：128MB    代码长度限制：64KB

背景 Background

裸体就意味着身体。

描述 Description

“第一分钟，X说，要有矩阵，于是便有了一个里面写满了0的n×m矩阵。
第二分钟，L说，要能修改，于是便有了将左上角为(a,b)，右下角为(c,d)的一个矩形区域内的全部数字加上一个值的操作。
第三分钟，k说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。
第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。
第五分钟，和雪说，要有耐心，于是便有了时间限制。
第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。
第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”
——《上帝造裸题的七分钟》
所以这个神圣的任务就交给你了。

输入格式 InputFormat

输入数据的第一行为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为小写。

输出格式 OutputFormat

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

样例输入 SampleInput [复制数据]

X 4 4
L 1 1 3 3 2
L 2 2 4 4 1
k 2 2 3 3

样例输出 SampleOutput [复制数据]

12

数据范围和注释 Hint

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

来源 Source

by XLk
状态
Accepted
题号 P1716
类型(?) 高级数据结构
通过 99人
提交 392次
通过率 25%
　　热烈庆祝AC200～～
　　这道题被hja坑去写二维线段树，结果不是TLE就是MLE，正确的做法是二维树状数组区间修改与区间查询，在网上找得到详细解法。
大体思路为维护a[][]使得前缀和sum[x][y]=segma(num[i][j])=segma(a[i][j]*(x-i+1)*(y-j+1))=segma(a[i][j]*(x+1)*(y+1)-(i+j)*a[i][j])
=segma(a[i][j])*(x+1)*(y+1)+segma(i*j*a[i][j])-segma(j*a[i][j])*(x+1)-segma(i*a[i][j])*(y+1)
最后，可以用4个树状数组分别维护上式中segma中引用部分。
　　下面贴上两种解法代码
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAXN 2050
 7 #define MAXT 5000000
 8 typedef int tree_t[MAXN][MAXN];
 9 tree_t tree1,tree2,tree3,tree4;
10 int lowbit(int x)
11 {
12         return x&(-x);
13 }
14 void add_val(tree_t tree,int x,int y,int v)
15 {
16 //        cout<<"ADD"<<x<<" "<<y<<" "<<v<<endl;
17         int i,j;
18         for (i=x;i<MAXN;i+=lowbit(i))
19         {
20                 for (j=y;j<MAXN;j+=lowbit(j))
21                 {
22                         tree[i][j]+=v;
23                 }
24         }
25 }
26 int query_sum(tree_t tree,int x,int y)
27 {
28         int i,j;
29         int ret=0;
30         for (i=x;i;i-=lowbit(i))
31         {
32                 for (j=y;j;j-=lowbit(j))
33                 {
34                         ret+=tree[i][j];
35                 }
36         }
37         return ret;
38 }
39 //sum(x,y)=segma(a[i][j]*(x-i+1)*(y-j+1))
40 //          =segma(a[i][j]*(x+1)*(y+1)-(i+j)*a[i][j]);
41 //          =segma(a[i][j])*(x+1)*(y+1)-segma((i+j)*a[i][j])
42 //
43 void add_matrix(int xl,int yl,int xr,int yr,int v)
44 {
45         add_val(tree1,xr+1,yr+1,v);
46         add_val(tree1,xl,yl,v);
47         add_val(tree1,xl,yr+1,-v);
48         add_val(tree1,xr+1,yl,-v);
49         add_val(tree2,xr+1,yr+1,v*(xr+1)*(yr+1));
50         add_val(tree2,xl,yl,v*(xl+0)*(yl+0));
51         add_val(tree2,xl,yr+1,-v*(xl+0)*(yr+1));
52         add_val(tree2,xr+1,yl,-v*(yl+0)*(xr+1));
53         
54         add_val(tree3,xr+1,yr+1,v*(xr+1));
55         add_val(tree3,xl,yl,v*(xl+0));
56         add_val(tree3,xl,yr+1,-v*(xl+0));
57         add_val(tree3,xr+1,yl,-v*(xr+1));
58 
59         add_val(tree4,xr+1,yr+1,v*(yr+1));
60         add_val(tree4,xl,yl,v*(yl+0));
61         add_val(tree4,xl,yr+1,-v*(yr+1));
62         add_val(tree4,xr+1,yl,-v*(yl+0));
63 
64 }    
65 int query_matrix(int x,int y)
66 {
67         if (!x || !y)return 0;
68         int ret=0;
69         int t;
70         ret+=query_sum(tree1,x,y)*(x+1)*(y+1);
71         ret-=(t=query_sum(tree3,x,y))*(y+1);
72         ret-=query_sum(tree4,x,y)*(x+1);
73         ret+=query_sum(tree2,x,y);
74         return ret;
75 }
76 int main()
77 {
78         freopen("input.txt","r",stdin);
79         int i,j,k;
80         int n,m;
81         int x,y,z;
82         char opt;
83         scanf("%c%d%d
",&opt,&n,&m);
84         int a,b,c,d,e;
85         while (~scanf("%c",&opt))
86         {
87                 if (opt=='L')
88                 {
89                         scanf("%d%d%d%d%d
",&a,&b,&c,&d,&e);
90                         add_matrix(a,b,c,d,e);
91                 }else
92                 {
93                         scanf("%d%d%d%d
",&a,&b,&c,&d);
94                         printf("%d
",query_matrix(a-1,b-1)+query_matrix(c,d)
95                                         -query_matrix(a-1,d)-query_matrix(c,b-1));
96                 }
97         }
98 }
树状数组解法
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 #define MAXN 2050
  7 #define MAXT 2000000
  8 #define midx ((tree[now].lx+tree[now].rx)>>1)
  9 #define midy ((tree[now].ly+tree[now].ry)>>1)
 10 #define tnly tree[now].ly
 11 #define tnry tree[now].ry
 12 #define tnlx tree[now].lx
 13 #define tnrx tree[now].rx
 14 #define tnlazy tree[now].lazy
 15 #define area(t) ((tree[t].rx-tree[t].lx+1)*(tree[t].ry-tree[t].ly+1))
 16 struct node
 17 {
 18         int ch[2][2];
 19         int lx,rx,ly,ry;
 20         int sum;
 21         int lazy=0;
 22 }tree[MAXT];
 23 int root=0,topt=0;
 24 void new_node(int &now,int lx,int rx,int ly,int ry)
 25 {
 26         if (lx>rx ||ly>ry)return ;
 27         now=++topt;
 28         tnlx=lx;
 29         tnrx=rx;
 30         tnly=ly;
 31         tnry=ry;
 32 }
 33 
 34 void down(int now)
 35 {
 36         if (!tree[now].ch[0][0])
 37                 new_node(tree[now].ch[0][0],tnlx,midx,tnly,midy);
 38         if (!tree[now].ch[0][1] && tnly<tnry)
 39                 new_node(tree[now].ch[0][1],tnlx,midx,midy+1,tnry);
 40         if (!tree[now].ch[1][0] && tnlx<tnrx)
 41                 new_node(tree[now].ch[1][0],midx+1,tnrx,tnly,midy);
 42         if (!tree[now].ch[1][1] && tnly<tnry && tnlx<tnrx)
 43                 new_node(tree[now].ch[1][1],midx+1,tnrx,midy+1,tnry);
 44         if (tnlazy)
 45         {
 46                 tree[tree[now].ch[0][0]].sum+=tnlazy*area(tree[now].ch[0][0]);
 47                 tree[tree[now].ch[0][0]].lazy+=tnlazy;
 48                 if (tnlx<tnrx)
 49                 {
 50                         tree[tree[now].ch[1][0]].sum+=tnlazy*area(tree[now].ch[1][0]);
 51                         tree[tree[now].ch[1][0]].lazy+=tnlazy;
 52                 }
 53                 if (tnly<tnry)
 54                 {
 55                         tree[tree[now].ch[0][1]].sum+=tnlazy*area(tree[now].ch[0][1]);
 56                         tree[tree[now].ch[0][1]].lazy+=tnlazy;
 57                 }
 58                 if (tnlx<tnrx && tnly<tnry)
 59                 {
 60                         tree[tree[now].ch[1][1]].sum+=tnlazy*area(tree[now].ch[1][1]);
 61                         tree[tree[now].ch[1][1]].lazy+=tnlazy;
 62                 }
 63                 tnlazy=0;
 64         }
 65 }
 66 void up(int now)
 67 {
 68         tree[now].sum=0;
 69         tree[now].sum+=tree[tree[now].ch[0][0]].sum;
 70         tree[now].sum+=tree[tree[now].ch[1][0]].sum;
 71         tree[now].sum+=tree[tree[now].ch[0][1]].sum;
 72         tree[now].sum+=tree[tree[now].ch[1][1]].sum;
 73 }
 74 void add_val(int &now,int lx,int rx,int ly,int ry,int v)
 75 {
 76         if (tnlx==lx &&tnly==ly && tnrx==rx &&tnry==ry)
 77         {
 78                 tree[now].sum+=v*(rx-lx+1)*(ry-ly+1);
 79                 tree[now].lazy+=v;
 80                 return ;
 81         }
 82         down(now);
 83         if (rx<=midx && ry<=midy)
 84         {
 85                 add_val(tree[now].ch[0][0],lx,rx,ly,ry,v);
 86                 up(now);
 87                 return ;
 88         }
 89         if (rx<=midx && ly> midy)
 90         {
 91                 add_val(tree[now].ch[0][1],lx,rx,ly,ry,v);
 92                 up(now);
 93                 return ;
 94         }
 95         if (lx> midx && ry<=midy)
 96         {
 97                 add_val(tree[now].ch[1][0],lx,rx,ly,ry,v);
 98                 up(now);
 99                 return ;
100         }
101         if (lx> midx && ly> midy)
102         {
103                 add_val(tree[now].ch[1][1],lx,rx,ly,ry,v);
104                 up(now);
105                 return ;
106         }
107         if (rx<=midx)
108         {
109                 add_val(tree[now].ch[0][0],lx,rx,ly,midy,v);
110                 add_val(tree[now].ch[0][1],lx,rx,midy+1,ry,v);
111                 up(now);
112                 return ;
113         }
114         if (lx> midx)
115         {
116                 add_val(tree[now].ch[1][0],lx,rx,ly,midy,v);
117                 add_val(tree[now].ch[1][1],lx,rx,midy+1,ry,v);
118                 up(now);
119                 return ;
120         }
121         if (ry<=midy)
122         {
123                 add_val(tree[now].ch[0][0],lx,midx,ly,ry,v);
124                 add_val(tree[now].ch[1][0],midx+1,rx,ly,ry,v);
125                 up(now);
126                 return ;
127         }
128         if (ly> midy)
129         {
130                 add_val(tree[now].ch[0][1],lx,midx,ly,ry,v);
131                 add_val(tree[now].ch[1][1],midx+1,rx,ly,ry,v);
132                 up(now);
133                 return ;
134         }
135         add_val(tree[now].ch[0][0],lx,midx,ly,midy,v);
136         add_val(tree[now].ch[0][1],lx,midx,midy+1,ry,v);
137         add_val(tree[now].ch[1][0],midx+1,rx,ly,midy,v);
138         add_val(tree[now].ch[1][1],midx+1,rx,midy+1,ry,v);
139         up(now);
140         return ;
141 }
142 int query(int now,int lx,int rx,int ly,int ry)
143 {
144         if (tree[now].lx==lx && tree[now].rx==rx &&
145                         tree[now].ly==ly && tree[now].ry==ry)
146         {
147                 return tree[now].sum;
148         }    
149         down(now);
150         int ans=0;
151         if (rx<=midx && ry<=midy)
152         {
153                 ans=query(tree[now].ch[0][0],lx,rx,ly,ry);
154                 return ans;
155         }
156         if (rx<=midx && ly> midy)
157         {
158                 ans=query(tree[now].ch[0][1],lx,rx,ly,ry);
159                 return ans;
160         }
161         if (lx> midx && ry<=midy)
162         {
163                 ans=query(tree[now].ch[1][0],lx,rx,ly,ry);
164                 return ans;
165         }
166         if (lx> midx && ly> midy)
167         {
168                 ans=query(tree[now].ch[1][1],lx,rx,ly,ry);
169                 return ans;
170         }
171         if (rx<=midx)
172         {
173                 ans=query(tree[now].ch[0][0],lx,rx,ly,midy);
174                 ans+=query(tree[now].ch[0][1],lx,rx,midy+1,ry);
175                 return ans;
176         }
177         if (lx> midx)
178         {
179                 ans=query(tree[now].ch[1][0],lx,rx,ly,midy);
180                 ans+=query(tree[now].ch[1][1],lx,rx,midy+1,ry);
181                 return ans;
182         }
183         if (ry<=midy)
184         {
185                 ans=query(tree[now].ch[0][0],lx,midx,ly,ry);
186                 ans+=query(tree[now].ch[1][0],midx+1,rx,ly,ry);
187                 return ans;
188         }
189         if (ly> midy)
190         {
191                 ans=query(tree[now].ch[0][1],lx,midx,ly,ry);
192                 ans+=query(tree[now].ch[1][1],midx+1,rx,ly,ry);
193                 return ans;
194         }
195         ans=query(tree[now].ch[0][0],lx,midx,ly,midy);
196         ans+=query(tree[now].ch[0][1],lx,midx,midy+1,ry);
197         ans+=query(tree[now].ch[1][0],midx+1,rx,ly,midy);
198         ans+=query(tree[now].ch[1][1],midx+1,rx,midy+1,ry);
199         up(now);
200         return ans;
201 }
202 int main()
203 {
204         //freopen("input.txt","r",stdin);
205         int i,j,k;
206         int n,m;
207         int x,y,z;
208         char opt;
209         scanf("%c%d%d
",&opt,&n,&m);
210         tree[1].lx=1;tree[1].rx=n;
211         tree[1].ly=1;tree[1].ry=m;
212         tree[1].sum=tree[1].lazy=0;
213         topt=1;
214         root=1;
215         int a,b,c,d,e;
216         while (~scanf("%s",&opt))
217         {
218                 if (opt=='L')
219                 {
220                         scanf("%d%d%d%d%d
",&a,&b,&c,&d,&e);
221                         add_val(root,a,c,b,d,e);
222                 }else
223                 {
224                         scanf("%d%d%d%d
",&a,&b,&c,&d);
225                         printf("%d
",query(root,a,c,b,d));
226                 }
227         }
228 
229 }
二维线段书解法
by mhy12345(http://www.cnblogs.com/mhy12345/) 未经允许请勿转载

本博客已停用，新博客地址：http://mhy12345.xyz

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/mhy12345/p/3956911.html