「BZOJ-1176」[Balkan2007]Mokia

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

链接

BZOJ-1176

输入

第一行两个整数,$S,W$;其中 $S$ 为矩阵初始值;$W$ 为矩阵大小
接下来每行为一下三种输入之一(不包含引号):
$“1$ $x$ $y$ $a”$
$“2 $ $x_1$ $y_1$ $x_2$ $y_2”$
$“3”$
输入1: 你需要把$(x,y)$(第$x$行第$y$列)的格子权值增加$a$
输入2: 你需要求出以左下角为$(x1,y1)$,右上角为$(x2,y2)$的矩阵内所有格子的权值和,并输出
输入3: 表示输入结束

输出

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

样例

输入

1
2
3
4
5
6
0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

输出

1
2
3
5

HINT

保证答案不会超过int范围

题解

CDQ分治

代码

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>
#include <ctime>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#define inf 1000000000
#define pa pair <int, int>
#define ll long long
using namespace std;
inline void R(int &v) {
static char ch;
v = 0;
bool p = 0;
do {
ch = getchar();
if (ch == '-')
p = 1;
} while ( !isdigit(ch) );
while ( isdigit(ch) ) {
v = ( v << 1 ) + ( v << 3 ) + ( ch ^ '0' );
ch = getchar();
}
if (p)
v = -v;
}
inline void R(long long &v) {
static char ch;
v = 0;
bool p = 0;
do {
ch = getchar();
if (ch == '-')
p = 1;
} while ( !isdigit(ch) );
while ( isdigit(ch) ) {
v = ( v << 1 ) + ( v << 3 ) + ( ch ^ '0' );
ch = getchar();
}
if (p)
v = -v;
}
int s, w, m;
int ans[10005];
int t[2000005];
int cnt9;
struct que {
int x, y, val, pos, id, kind;
} q[200005], temp[200005];
bool operator < (que a, que b) {
if (a.x == b.x && a.y == b.y) return a.kind < b.kind;
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
void add(int x, int val) {
for (int i = x; i <= w; i += i & - i) t[i] += val;
}
int query(int x) {
int temp = 0;
for (int i = x; i; i -= i & - i) temp += t[i];
return temp;
}
void mergesort(int l, int r) {
if (l == r) return;
int mid = ( l + r ) >> 1, l1 = l, l2 = mid + 1;
for (int i = l; i <= r; i++) {
if (q[i].id <= mid && !q[i].kind) add(q[i].y, q[i].val);
if (q[i].id > mid && q[i].kind) ans[q[i].pos] += q[i].val * query(q[i].y);
}
for (int i = l; i <= r; i++)
if (q[i].id <= mid && !q[i].kind) add(q[i].y, -q[i].val);
for (int i = l; i <= r; i++)
if (q[i].id <= mid) temp[l1++] = q[i];
else temp[l2++] = q[i];
for (int i = l; i <= r; i++)
q[i] = temp[i];
mergesort(l, mid), mergesort(mid + 1, r);
}
int main() {
R(s), R(w);
int kind;
int x1, y1, x2, y2;
while (1) {
R(kind);
if (kind == 1) {
R(q[++m].x), R(q[m].y), R(q[m].val);
q[m].id = m;
} else if (kind == 2) {
R(x1), R(y1), R(x2), R(y2);
int pos = ++cnt9;
q[++m].pos = pos, q[m].id = m, q[m].x = x1 - 1, q[m].y = y1 - 1, q[m].val = 1, q[m].kind = 1;
q[++m].pos = pos, q[m].id = m, q[m].x = x2, q[m].y = y2, q[m].val = 1, q[m].kind = 1;
q[++m].pos = pos, q[m].id = m, q[m].x = x1 - 1, q[m].y = y2, q[m].val = -1, q[m].kind = 1;
q[++m].pos = pos, q[m].id = m, q[m].x = x2, q[m].y = y1 - 1, q[m].val = -1, q[m].kind = 1;
} else break;
}
sort(q + 1, q + m + 1);
mergesort(1, m);
for (int i = 1; i <= cnt9; i++)
cout << ans[i] << '\n';
return 0;
}
文章目录
  1. 1. 链接
  2. 2. 输入
  3. 3. 输出
  4. 4. 样例
    1. 4.1. 输入
    2. 4.2. 输出
  5. 5. HINT
  6. 6. 题解
  7. 7. 代码