关键词:CDQ分治  树套树 相关题目:[BOI2007]Mokia 摩基亚 CDQ分治的入门题,刚学练练手2333...

Description

维护一个 W*W 的矩阵,初始值均为 S .每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数 M<=160000 ,询问数 Q<=10000, W<=2000000.

Input&Output

Input 第一行两个整数, S,W ;其中 S 为矩阵初始值; W 为矩阵大小 接下来每行为一下三种输入之一(不包含引号):

“1 x y a” “2 x1 y1 x2 y2” “3”

输入1:你需要把(x,y)(第x行第y列)的格子权值增加a 输入2:你需要求出以左上角为(x1,y1),右下角为(x2,y2)的矩阵内所有格子的权值和,并输出 输入3:表示输入结束

Output 对于每个输入2,输出一行,即输入2的答案

Sample Input

0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

Sample Output

3
5

HINT

保证答案不会超过int范围

Solution

我们可以先将操作离线,然后将所有操作按照 x 排序,再进行 CDQ分治。先计算前一半操作对后面询问的影响,接着将前、后一半操作分配到两边,再将操作二分。(保证按 x 有序)。

计算答案的具体操作:我们可以将询问操作分为四个前缀和查询。

如:查询区间 (lx, ly), (rx, ry); 可以看做: (0,0), (rx, ry) 含点个数 + (0,0), (lx, ly) 含点个数 - (0,0), (lx, ry) 含点个数 - (0,0), (rx, ly) 含点个数

我们可以将用树状数组维护 yi 的前缀和,因为后一半操作的 x 大于前一半操作的 x 。所以只需查询 y 的前缀和就好啦。

(详见代码)

AC代码

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
70
71
72
73
74
75
// luogu-judger-enable-o2
#include <cstdio>
#include <algorithm>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)

struct node {
int id, x, y, d, pos, o;
// 编号 x y 数量 组 优先级
} a[200020];
int cnt=0, ans[10020], group=0;
int W;

struct BIT {
int t[2000020];
inline int lowbit(int x) {return x&(-x);}
inline void update(int x, int k) {
while(x <= W) t[x] += k, x+=lowbit(x);
}
inline int query(int x) {
int res = 0;
while(x) res += t[x], x-=lowbit(x);
return res;
}
} T;
inline bool cmp(const node _A, const node _B) {
if(_A.x != _B.x) return _A.x < _B.x;
if(_A.y != _B.y) return _A.y < _B.y;
return _A.o > _B.o;
}

node temp[200020];

inline void cdq(int l, int r) {
if(l==r) return ;
int mid = (l+r)>>1;
rep(i,l,r) {
if(a[i].id<=mid && a[i].o==1) T.update(a[i].y, a[i].d);
if(a[i].id>mid && a[i].o==0) ans[a[i].pos] += T.query(a[i].y)*a[i].d;
}
rep(i,l,r)
if(a[i].id<=mid && a[i].o==1) T.update(a[i].y, -a[i].d);

int l1=l, l2=mid+1;
rep(i,l,r)
if(a[i].id <= mid) temp[l1++] = a[i];
else temp[l2++] = a[i];
rep(i,l,r) a[i] = temp[i];

cdq(l, mid), cdq(mid+1, r);
}

int main() {
scanf("0 %d", &W);
int opt, x, y, d, lx, ly, rx, ry;
while(scanf("%d", &opt), opt!=3) {
if(opt == 1) {
scanf("%d%d%d", &x, &y, &d);
a[++cnt] = (node){cnt, x, y, d, 0, 1};
}
else {
scanf("%d%d%d%d", &lx, &ly, &rx, &ry);
a[++cnt] = (node){cnt, lx-1, ly-1, 1, ++group, 0};
a[++cnt] = (node){cnt, rx, ry, 1, group, 0};
a[++cnt] = (node){cnt, lx-1, ry, -1, group, 0};
a[++cnt] = (node){cnt, rx, ly-1, -1, group, 0};
}
}
sort(a+1, a+1+cnt, cmp);
cdq(1, cnt);

rep(i,1,group)
printf("%d\n", ans[i]);
}