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
| #include <cstdio>
#include <vector>
#include <algorithm>
#define fi first
#define se second
#define eb emplace_back
using namespace std;
template <class Type>
void read (Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
if (c == '-') flag = true;
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
if (flag) x = ~x + 1;
}
template <class Type, class ...Rest>
void read (Type &x, Rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
if (x < 0) putchar('-'), x = ~x + 1;
if (x > 9) write(x / 10);
putchar('0' + x % 10);
}
typedef long long L;
typedef pair <int, L> PIL;
const L inf = 1e16;
const int N = 1e5 + 10, M = 310;
vector <int> wx, wy;
vector <PIL> tr[N];
int tot, id[N], st[N], ed[N];
L Tr[M][N];
int n, m, nx, ny, u[N], v[N], w[N];
int get (vector <int> &ws, int *w)
{
for (int i = 1; i <= n; ++i) ws.eb(w[i]);
sort(ws.begin(), ws.end());
ws.erase(unique(ws.begin(), ws.end()), ws.end());
for (int i = 1; i <= n; ++i)
w[i] = upper_bound(ws.begin(), ws.end(), w[i]) - ws.begin();
return ws.size();
}
void add (int x, int y, int k)
{
for (int i = x; i <= tot; i += i & -i)
for (int j = y; j <= ny; j += j & -j)
Tr[i][j] += k;
}
L query (int x, int y)
{
L res = 0;
for (int i = x; i; i -= i & -i)
for (int j = y; j; j -= j & -j)
res += Tr[i][j];
return res;
}
L calc (int x, int y)
{
x = upper_bound(wx.begin(), wx.end(), x) - wx.begin();
y = upper_bound(wy.begin(), wy.end(), y) - wy.begin();
if (!x || !y) return 0;
L res = query(id[x] - 1, y);
for (int i = st[id[x]]; i <= x; ++i)
res += (--upper_bound(tr[i].begin(), tr[i].end(), (PIL){ y, inf }))->se;
return res;
}
int main ()
{
read(n, m);
for (int i = 1; i <= n; ++i)
read(u[i], v[i], w[i]);
nx = get(wx, u), ny = get(wy, v);
int B = nx / (M - 1) + 1;
for (int i = 1; i <= nx; ++i)
id[i] = (i - 1) / B + 1;
tot = id[nx];
for (int i = 1; i <= tot; ++i)
st[i] = ed[i - 1] + 1, ed[i] = ed[i - 1] + B;
ed[tot] = nx;
for (int i = 1; i <= n; ++i)
{
tr[u[i]].eb(v[i], w[i]);
add(id[u[i]], v[i], w[i]);
}
for (int i = 1; i <= nx; ++i)
{
tr[i].eb(0, 0);
sort(tr[i].begin(), tr[i].end());
for (int j = 1; j < tr[i].size(); ++j)
tr[i][j].se = tr[i][j - 1].se + tr[i][j].se;
}
for (int x1, y1, x2, y2; m; --m, puts(""))
{
read(x1, y1, x2, y2); --x1, --y1;
write(calc(x2, y2) + calc(x1, y1) - calc(x1, y2) - calc(x2, y1));
}
return 0;
}
|