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
| struct Point {
int x, y;
friend bool operator == (const Point &u, const Point &v) { return u.x == v.x && u.y == v.y; }
} a[maxn];
inline bool cmpx(const Point &u, const Point &v) {
if (u.x == v.x) return u.y < v.y;
return u.x < v.x;
}
inline bool cmpy(const Point &u, const Point &v) {
if (u.y == v.y) return u.x < v.x;
return u.y < v.y;
}
vector<bool(*)(const Point &u, const Point &v)> cmp;
void init_cmp() {
cmp.push_back(cmpx);
cmp.push_back(cmpy);
}
#define lc i << 1
#define rc i << 1 | 1
struct KDtree {
int xl, xr, yl, yr, v, tag;
Point p;
} T[maxn * 4];
inline void maintain(int i) {
T[i].xl = min(T[lc].xl, T[rc].xl);
T[i].xr = max(T[lc].xr, T[rc].xr);
T[i].yl = min(T[lc].yl, T[rc].yl);
T[i].yr = max(T[lc].yr, T[rc].yr);
}
inline void Update(int i, int v) {
}
inline void pushdown(int i) {
int &tag = T[i].tag; if (!tag) return ;
Update(lc, v); Update(rc, v);
tag = 0;
}
void build(int i, int l, int r, int d) {
T[i].tag = 0;
if (l == r) return T[i] = { a[l].x, a[l].x, a[l].y, a[l].y, 1, 0, a[l] }, void();
int m = l + r >> 1; nth_element(a + l, a + m, a + r + 1, cmp[d]); T[i].p = a[m];
build(lc, l, m, d ^ 1); build(rc, m + 1, r, d ^ 1);
maintain(i);
}
void update(int i, int xl, int xr, int yl, int yr, int v) {
if (max(T[i].xl, xl) > min(T[i].xr, xr) || max(T[i].yl, yl) > min(T[i].yr, yr)) return ;
if (xl <= T[i].xl && T[i].xr <= xr && yl <= T[i].yl && T[i].yr <= yr)
return Update(i, v);
pushdown(i);
update(lc, xl, xr, yl, yr, v); update(rc, xl, xr, yl, yr, v);
maintain(i);
}
int query(int i, int l, int r, const Point &p, int d) {
if (l == r) return T[i].v;
int m = l + r >> 1; pushdown(i);
if (T[i].p == p || cmp[d](p, T[i].p))
return query(lc, l, m, p, d ^ 1);
else return query(rc, m + 1, r, p, d ^ 1);
}
|