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 4L 1 1 3 3 2L 2 2 4 4 1k 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%
提交评测
我的记录
查看本题解答排行前往本题讨论区阅读本题题解查看本题数据查看参考代码(VIP)
热烈庆祝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\n",&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\n",&a,&b,&c,&d,&
e);
90 add_matrix(a,b,c,d,e);
91 }
else
92 {
93 scanf(
"%d%d%d%d\n",&a,&b,&c,&
d);
94 printf(
"%d\n",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\n",&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\n",&a,&b,&c,&d,&
e);
221 add_val(root,a,c,b,d,e);
222 }
else
223 {
224 scanf(
"%d%d%d%d\n",&a,&b,&c,&
d);
225 printf(
"%d\n",query(root,a,c,b,d));
226 }
227 }
228
229 }
二维线段书解法
转载于:https://www.cnblogs.com/mhy12345/p/3956911.html
