最近忽然发现 BZOJ 的权限题还是很多的(可能是因为以前搜不到就不搜了现在上 DARKBZOJ ),看来还是得众筹买个权限号了(雾

这是一道傻逼数据结构题,由于数据范围小,各种奇葩算法随便过。本菜鸡就写了个普通的树状数组套莫队,各位大佬不要见笑。

代码:

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
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long
#define rep(i,l,r) for (int i = l; i <= r; i++)

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 100010, maxm = 100010;

#define lowbit(x) ((x)&(-(x)))

int n, m, l, r, x, y, tn, ql, qr, sqn;
int a[maxn], b[maxn], bln[maxn], cnt[maxn], s[2][maxn], ans[2][maxm];

struct query {
int l, r, x, y, i;
} q[maxm];
bool cmp(query x, query y) {
if (bln[x.l] ^ bln[y.l])
return x.l < y.l;
return x.r < y.r;
}

inline void modify(int i, int x, int k) {
i++;
for (; i <= n + 1; i += lowbit(i))
s[k][i] += x;
}

inline int query(int i, int k) {
int ret = 0;
i++;
for (; i >= 2; i -= lowbit(i))
ret += s[k][i];
return ret;
}

inline void add(int x) {
if (!cnt[x]) {
modify(x, 1, 1);
}
modify(x, 1, 0);
cnt[x]++;
}

inline void del(int x) {
modify(x, -1, 0);
cnt[x]--;
if (!cnt[x]) {
modify(x, -1, 1);
}
}

int main() {

n = read(), m = read(), sqn = n / sqrt(m * 2.0 / 3);
if (sqn == 0) sqn++;
for (int i = 1; i <= n; i++)
bln[i] = i / sqn;

for (int i = 1; i <= n; i++)
a[i] = read();
for (int i = 1; i <= n; i++)
b[i] = a[i];
std::sort(b + 1, b + n + 1);
tn = std::unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; i++)
a[i] = std::lower_bound(b + 1, b + tn + 1, a[i]) - b;

for (int i = 1; i <= m; i++) {
q[i].l = read(), q[i].r = read();
q[i].x = read(), q[i].y = read();
q[i].i = i;
}
std::sort(q + 1, q + m + 1, cmp);

ql = 1, qr = 0;
for (int i = 1; i <= m; i++) {
l = q[i].l, r = q[i].r;
x = q[i].x, y = q[i].y;
x = std::lower_bound(b + 1, b + tn + 1, x) - b - 1;
y = std::upper_bound(b + 1, b + tn + 1, y) - b - 1;
while (ql < l) del(a[ql++]);
while (ql > l) add(a[--ql]);
while (qr > r) del(a[qr--]);
while (qr < r) add(a[++qr]);
ans[0][q[i].i] = query(y, 0) - query(x, 0);
ans[1][q[i].i] = query(y, 1) - query(x, 1);
}

for (int i = 1; i <= m; i++)
printf("%d %d\n", ans[0][i], ans[1][i]);

return 0;
}