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
| #include "ybwhead/ios.h"
using namespace std;
const int N = 200005;
struct point
{
int x[2], w;
} p[N];
struct node
{
int mi[2], mx[2], sum, ls, rs, sz;
point tp;
} tr[N];
int n, ans, rt, WD, top, cur, rub[N];
int operator<(point a, point b) { return a.x[WD] < b.x[WD]; }
int newnode()
{
if (top)
return rub[top--];
else
return ++cur;
}
void up(int k)
{
int l = tr[k].ls, r = tr[k].rs;
for (int i = 0; i <= 1; ++i)
{
tr[k].mi[i] = tr[k].mx[i] = tr[k].tp.x[i];
if (l)
tr[k].mi[i] = min(tr[k].mi[i], tr[l].mi[i]);
if (r)
tr[k].mi[i] = min(tr[k].mi[i], tr[r].mi[i]);
if (l)
tr[k].mx[i] = max(tr[k].mx[i], tr[l].mx[i]);
if (r)
tr[k].mx[i] = max(tr[k].mx[i], tr[r].mx[i]);
}
tr[k].sum = tr[l].sum + tr[r].sum + tr[k].tp.w, tr[k].sz = tr[l].sz + tr[r].sz + 1;
}
int build(int l, int r, int wd)
{
if (l > r)
return 0;
int mid = (l + r) >> 1, k = newnode();
WD = wd, nth_element(p + l, p + mid, p + r + 1), tr[k].tp = p[mid];
tr[k].ls = build(l, mid - 1, wd ^ 1), tr[k].rs = build(mid + 1, r, wd ^ 1);
up(k);
return k;
}
void pia(int k, int num)
{
if (tr[k].ls)
pia(tr[k].ls, num);
p[tr[tr[k].ls].sz + num + 1] = tr[k].tp, rub[++top] = k;
if (tr[k].rs)
pia(tr[k].rs, num + tr[tr[k].ls].sz + 1);
}
void check(int &k, int wd)
{
if (tr[k].sz * 0.75 < tr[tr[k].ls].sz || tr[k].sz * 0.75 < tr[tr[k].rs].sz)
pia(k, 0), k = build(1, tr[k].sz, wd);
}
void ins(int &k, point tmp, int wd)
{
if (!k)
{
k = newnode(), tr[k].ls = tr[k].rs = 0, tr[k].tp = tmp, up(k);
return;
}
if (tmp.x[wd] <= tr[k].tp.x[wd])
ins(tr[k].ls, tmp, wd ^ 1);
else
ins(tr[k].rs, tmp, wd ^ 1);
up(k), check(k, wd);
}
int in(int x1, int y1, int x2, int y2, int X1, int Y1, int X2, int Y2)
{
return (X1 >= x1 && X2 <= x2 && Y1 >= y1 && Y2 <= y2);
}
int out(int x1, int y1, int x2, int y2, int X1, int Y1, int X2, int Y2)
{
return (x1 > X2 || x2 < X1 || y1 > Y2 || y2 < Y1);
}
int query(int k, int x1, int y1, int x2, int y2)
{
if (!k)
return 0;
int re = 0;
if (in(x1, y1, x2, y2, tr[k].mi[0], tr[k].mi[1], tr[k].mx[0], tr[k].mx[1]))
return tr[k].sum;
if (out(x1, y1, x2, y2, tr[k].mi[0], tr[k].mi[1], tr[k].mx[0], tr[k].mx[1]))
return 0;
if (in(x1, y1, x2, y2, tr[k].tp.x[0], tr[k].tp.x[1], tr[k].tp.x[0], tr[k].tp.x[1]))
re += tr[k].tp.w;
re += query(tr[k].ls, x1, y1, x2, y2) + query(tr[k].rs, x1, y1, x2, y2);
return re;
}
int main()
{
int bj, x1, y1, x2, y2;
yin >> n;
while (1)
{
yin >> bj;
if (bj == 3)
break;
yin >> x1 >> y1 >> x2;
x1 ^= ans;
y1 ^= ans;
x2 ^= ans;
if (bj == 1)
ins(rt, (point){x1, y1, x2}, 0);
else
{
yin >> y2;
y2 ^= ans;
ans = query(rt, x1, y1, x2, y2);
yout << ans << endl;
}
}
return 0;
}
|