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
| #include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
int lstans;
int Read() { int k=read(); return k^lstans; }
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
#define N 500010
void Mn(int &a, int b) { a = min(a, b); }
void Mx(int &a, int b) { a = max(a, b); }
struct node { int x[2], v; } t[N];
int n, m, i, j, k, T;
int s[N], ls[N], rs[N];
int mn[N][2], mx[N][2], xl, xr, yl, yr, op, ans;
int b[N], cnt, rt[22];
void update(int k) {
s[k] = s[ls[k]] + s[rs[k]] + t[k].v;
for(int i = 0; i <= 1; ++i) {
mn[k][i] = mx[k][i] = t[k].x[i];
if(ls[k]) Mn(mn[k][i], mn[ls[k]][i]), Mx(mx[k][i], mx[ls[k]][i]);
if(rs[k]) Mn(mn[k][i], mn[rs[k]][i]), Mx(mx[k][i], mx[rs[k]][i]);
}
}
void print(int x) {
if(ls[x]) print(ls[x]);
if(rs[x]) print(rs[x]);
}
int build(int l, int r, int o) {
int p = (l + r + 1) >> 1;
nth_element(b+l, b+p, b+r+1, [o](int x, int y) { return t[x].x[o] < t[y].x[o]; });
int x = b[p]; ls[x] = rs[x] = 0;
if(l < p) ls[x] = build(l, p-1, o^1);
if(r > p) rs[x] = build(p+1, r, o^1);
update(x);
return x;
}
void append(int x) {
if(!x) return ;
b[++cnt]=x;
append(ls[x]);
append(rs[x]);
}
int qry(int x) {
if(!x) return 0;
if(mn[x][0] >= xl && mx[x][0] <= xr && mn[x][1] >= yl && mx[x][1] <= yr) return s[x];
debug("> %d [%d %d] [%d %d] (%d) (%d)\n", x, mn[x][0], mx[x][0], mn[x][1], mx[x][1], ls[x], rs[x]);
if(mn[x][0] > xr || mx[x][0] < xl || mn[x][1] > yr || mx[x][1] < yl) return 0;
int ans = qry(ls[x]) + qry(rs[x]);
if(t[x].x[0] >= xl && t[x].x[0] <= xr && t[x].x[1] >= yl && t[x].x[1] <= yr) ans += t[x].v;
return ans;
}
signed main()
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
T=read(); lstans=0;
while(1) {
op=read();
if(op == 3) return 0;
if(op==1) {
++n;
t[n].x[0]=Read(); t[n].x[1]=Read(); t[n].v=Read();
debug("Point(%d %d) %d\n", t[n].x[0], t[n].x[1], t[n].v);
b[cnt = 1] = n;
for(i=0; i<=20; ++i) {
if(!rt[i]) { rt[i] = build(1, cnt, 0); break; }
append(rt[i]); rt[i]=0;
}
}
else {
ans = 0;
xl=Read(); yl=Read(); xr=Read(); yr=Read();
debug("[%d %d] [%d %d]\n", xl, xr, yl, yr);
for(i=0; i<=20; ++i) if(rt[i]) ans += qry(rt[i]);
printf("%d\n", lstans = ans);
}
}
return 0;
}
|
