「BZOJ-1176」[Balkan2007]Mokia-k-d树

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

链接

BZOJ-1176

输入

第一行两个整数,$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:表示输入结束

输出

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

样例

输入

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$ 分治,但此题直接写 k-d树 就可以直接卡过了…

代码

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
const int IN_LEN = 10000000, OUT_LEN = 10000000;
inline int nextChar() {
static char buf[IN_LEN], *h, *t;
if (h == t) {
t = (h = buf) + fread(buf, 1, IN_LEN, stdin);
if (h == t) return -1;
}
return *h++;
}
template<class T>
inline bool read(T &x) {
static bool iosig = 0;
static char c;
for (iosig = 0, c = nextChar(); !isdigit(c); c = nextChar()) {
if (c == -1) return false;
if (c == '-') iosig = 1;
}
for (x = 0; isdigit(c); c = nextChar()) x = (x << 1) + (x << 3) + (c ^ '0');
if (iosig) x = -x;
return true;
}
char obuf[OUT_LEN], *oh = obuf;
inline void writeChar(const char c) {
if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
*oh++ = c;
}
template<class T>
inline void write(T x) {
static int buf[30], cnt;
if (!x) writeChar(48);
else {
if (x < 0) writeChar('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) writeChar(buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
struct Point {
int pos[2];
Point(int a, int b) { pos[0] = a, pos[1] = b; }
inline int &operator [] (int x) { return pos[x]; }
inline bool operator < (const Point &p) const { return pos[0] < p.pos[0] && pos[1] < p.pos[1]; }
inline bool operator == (const Point &p) const { return pos[0] == p.pos[0] && pos[1] == p.pos[1]; }
inline bool operator <= (const Point &p) const { return pos[0] <= p.pos[0] && pos[1] <= p.pos[1]; }
};
inline void updateMin(Point &a, Point &b) { a[0] = std::min(a[0], b[0]), a[1] = std::min(a[1], b[1]); }
inline void updateMax(Point &a, Point &b) { a[0] = std::max(a[0], b[0]), a[1] = std::max(a[1], b[1]); }
bool cmp;
struct Node {
Node *lc, *rc;
Point p, l, r;
int v, sum, size;
Node(const Point &p, int v) : lc(0), rc(0), p(p), l(p), r(p), v(v), sum(v), size(1) {}
inline int querySum(Point &l, Point &r) {
if (l <= this->l && this->r <= r) return this->sum;
if (l[0] > this->r[0] || l[1] > this->r[1] || r[0] < this->l[0] || r[1] < this->l[1]) return 0;
register int sum = 0;
if (l <= p && p <= r) sum += v;
if (lc) sum += lc->querySum(l, r);
if (rc) sum += rc->querySum(l, r);
return sum;
}
inline void clear() { lc = rc = 0, l = r = p, sum = v, size = 1; }
inline void *operator new(size_t) {
static Node *s, *t;
static size_t size = sizeof(Node) << 12;
if (s == t) s = (Node*)malloc(size), t = s + (1 << 12);
return s++;
}
inline void update() {
l = r = p, sum = v, size = 1;
if (lc) updateMin(l, lc->l), updateMax(r, lc->r), sum += lc->sum, size += lc->size;
if (rc) updateMin(l, rc->l), updateMax(r, rc->r), sum += rc->sum, size += rc->size;
}
} *pool[200001];
inline bool less(Node *a, Node *b) { return a->p[cmp] < b->p[cmp]; }
int top = 0;
const double A = 0.7, B = log(1.0 / 0.7);
struct KDimensionalTree {
Node *rt;
KDimensionalTree(): rt(0) {}
inline bool insert(Node *&x, Node *y, int h = 0, bool comp = 0) {
if (!x) {
x = new Node(*y);
return h > log(rt->size) / B;
}
if (x->p == y->p) return x->v += y->v, x->sum += y->v, 0;
cmp = comp;
if (less(y, x)) {
bool kre = insert(x->lc, y, h + 1, !comp);
x->update();
if (kre) return x->lc->size > x->size * A ? reBuild(x, comp), 0 : 1;
return 0;
} else {
bool kre = insert(x->rc, y, h + 1, !comp);
x->update();
if (kre) return x->rc->size > x->size * A ? reBuild(x, comp), 0 : 1;
return 0;
}
}
inline void insert(const Point &p, int v) { Node it(p, v); insert(rt, &it); }
inline void tour(Node *x) {
if (!x) return;
tour(x->lc), pool[++top] = x, tour(x->rc), x->clear();
}
inline void reBuild(Node *&x, bool comp, int lc, int rc) {
if (rc < lc) { x = 0; return; }
cmp = comp;
int mid = lc + rc >> 1;
std::nth_element(pool + lc, pool + mid, pool + rc + 1, less);
x = pool[mid], reBuild(x->lc, !comp, lc, mid - 1), reBuild(x->rc, !comp, mid + 1, rc), x->update();
}
inline void reBuild(Node *&x, bool comp) { top = 0, tour(x), reBuild(x, comp, 1, top); }
inline int query(int x1, int y1, int x2, int y2) {
if (!rt) return 0;
Point l(x1, y1);
Point r(x2, y2);
return rt->querySum(l, r);
}
} tr;
int s, n, o, x, y, a, z, w;
int main() {
read(s), read(n);
while (read(o)) {
if (o == 3) break;
if (o == 1) read(x), read(y), read(a), tr.insert(Point(x, y), a);
else read(x), read(y), read(z), read(w), write(tr.query(x, y, z, w) + (z - x + 1) * (w - y + 1) * s), writeChar('\n');
}
flush();
return 0;
}
分享到