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
| #include <bits/stdc++.h>
#include "ybwhead/ios.h"
const int maxn = 1e5 + 10;
struct pos
{
bool op;
int x, y;
long long v;
int id;
} e[maxn << 2];
int w;
int tot, cnt;
bool cmp(pos a, pos b) { return a.x < b.x; }
#define lowbit(x) x & -x
long long a[maxn << 6];
long long s;
long long ans[maxn];
void add(int p, long long x)
{
for (; p <= w + 1; p += lowbit(p))
a[p] += x;
}
int q(int p)
{
long long ans = 0;
for (; p; p -= lowbit(p))
ans += a[p];
return ans;
}
void cdq(int l, int r)
{
if (l == r)
return;
int mid = (l + r) >> 1;
cdq(l, mid);
sort(e + l, e + mid + 1, cmp);
cdq(mid + 1, r);
sort(e + mid + 1, e + r + 1, cmp);
int p1 = l, p2 = mid + 1;
while (p2 <= r)
{
while (p1 <= mid && e[p1].x <= e[p2].x)
{
if (e[p1].op == 0)
add(e[p1].y, e[p1].v);
p1++;
}
if (e[p2].op == 1)
ans[e[p2].id] += q(e[p2].y) * e[p2].v;
p2++;
}
p1 = l, p2 = mid + 1;
while (p2 <= r)
{
while (p1 <= mid && e[p1].x <= e[p2].x)
{
if (e[p1].op == 0)
add(e[p1].y, -e[p1].v);
p1++;
}
// if (e[p2].op == 2)
// ans[e[p2].id] += q(e[p2].y) * e[p2].v;
p2++;
}
return;
}
int main()
{
yin >> s >> w;
int op = 0;
while (yin >> op && op != 3)
{
int x, y, x1, y1;
long long v;
if (op == 1)
{
yin >> x >> y >> v;
x++;
y++;
e[++tot] = {0, x, y, v, 0};
}
else
{
yin >> x >> y >> x1 >> y1;
x++;
y++;
x1++;
y1++;
++cnt;
e[++tot] = {1, x - 1, y - 1, 1, cnt};
e[++tot] = {1, x1, y1, 1, cnt};
e[++tot] = {1, x - 1, y1, -1, cnt};
e[++tot] = {1, x1, y - 1, -1, cnt};
}
}
cdq(1, tot);
for (int i = 1; i <= cnt; i++)
yout << ans[i] + s << endl;
return 0;
}
|
