题目背景
裸体就意味着身体。
题目描述
“第一分钟，X说，要有矩阵，于是便有了一个里面写满了 00 的 n×mn×m 矩阵。
第二分钟，L说，要能修改，于是便有了将左上角为 (a,b)(a,b) ，右下角为 (c,d)(c,d) 的一个矩形区域内的全部数字加上一个值的操作。
第三分钟，k说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。
第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。
第五分钟，和雪说，要有耐心，于是便有了时间限制。
第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。
第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”
——《上帝造裸题的七分钟》
所以这个神圣的任务就交给你了。
输入格式
输入数据的第一行为X n m，代表矩阵大小为 $n \times m$ 。
从输入数据的第二行开始到文件尾的每一行会出现以下两种操作：
L a b c d delta —— 代表将 $(a,b),(c,d)$ 为顶点的矩形区域内的所有数字加上$delta$。
k a b c d —— 代表求 $(a,b),(c,d)$ 为顶点的矩形区域内所有数字的和。
请注意， $ k $ 为小写。
输出格式
针对每个 $k$ 操作，在单独的一行输出答案。
输入样例
X 4 4
L 1 1 3 3 2
L 2 2 4 4 1
k 2 2 3 3
输出样例
12
说明
对于10%的数据， $ 1 ≤ n ≤ 16, 1 ≤ m ≤ 16 $ , 操作不超过200个.
对于60%的数据， $1 ≤ n ≤ 512, 1 ≤ m ≤ 512$ .
对于100%的数据， $1 ≤ n ≤ 2048, 1 ≤ m ≤ 2048, -500 ≤ delta ≤ 500$ ,操作不超过200000个,保证运算过程中及最终结果均不超过32位带符号整数类型的表示范围。
by XLk
Solution
这道题真的是哔了狗了，一大堆玄学卡常及优化，最后还开了O2，才勉强AC。
这道题差不多就是个二维树状数组的模板，但有1个坑点要注意：
区间修改坐标要+1，区间查询坐标不能+1
就因为这个被卡了好久。。。。
直接上代码
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iomanip>
#define lowbit(x) ((x)&(-(x)))
#define R register
#define ll long long
using namespace std;
inline void read(int &w) {
int f=1;
w=0;
char s=getchar();
while(s<'0'||s>'9') {if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9') {w=w*10+s-'0';s=getchar();}
w*=f;
}
inline void write(int x) {
if(x<0) {putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
int n,m;
struct BIT_2D {
int a[4][2049][2049];
void up(int x,int y,int delta) {
if (x<1 || n<x || y<1 || m<y) return;
for (int i=x; i<=n; i+=lowbit(i)) {
for (int j=y; j<=m; j+=lowbit(j)) {
a[0][i][j]+=delta;
a[1][i][j]+=delta*y;
a[2][i][j]+=delta*x;
a[3][i][j]+=delta*x*y;
}
}
}
int sum(int x,int y) {
int res=0;
for (int i=x; i; i-=lowbit(i)) {
for (int j=y; j; j-=lowbit(j)) {
res=res+(x+1)*(y+1)*a[0][i][j]-(x+1)*a[1][i][j]-(y+1)*a[2][i][j]+a[3][i][j];
}
}
return res;
}
}tree;
int main() {
char flag;
cin>>flag;
cin>>n>>m;
while(scanf("\n%c ",&flag)!=EOF) {
int x1,y1,x2,y2;
int k;
if(flag=='L') {
read(x1);read(y1);read(x2);read(y2);read(k);
x1++;x2++;y1++;y2++;
tree.up(x2,y2,k);
tree.up(x1-1,y2,-k);
tree.up(x2,y1-1,-k);
tree.up(x1-1,y1-1,k);
} else {
read(x1);read(y1);read(x2);read(y2);
int p=tree.sum(x2,y2)-tree.sum(x1-1,y2)-tree.sum(x2,y1-1)+tree.sum(x1-1,y1-1);
write(p);
puts("");
}
}
return 0;
}
|
