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
122
123
124
125
126
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 500000, maxb = 1250;
const int B1 = 450, B2 = 400;
int n;
int blg[maxn + 5];
int lp[maxb + 5], rp[maxb + 5];
int a[maxn + 5];
vector<pair<int, int>> seq[maxn + 5];
pair<int, int> q1[maxn + 5];
int t[maxn + 5];
#define lowbit(x) (x & (-x))
void modify(int x, int v) {
while (x <= n) {
t[x] += v;
x += lowbit(x);
}
}
int query(int x) {
int res = 0;
while (x > 0) {
res += t[x];
x -= lowbit(x);
}
return res;
}
long long rude(int l) {
long long res = 0;
int j = 1;
for (int i = 1; i <= l; i++) {
while (j <= l && q1[j].first != q1[i].first)
modify(q1[j++].second, 1);
res += query(q1[i].second - 1);
}
if (l < n / 500)
for (int i = 1; i < j; i++)
modify(q1[i].second, -1);
else
memset(t, 0, sizeof(t));
return res;
}
struct offline {
int id, p, z;
};
vector<offline> q2[maxb + 5];
int sum[maxn + 5];
long long pre[maxn + 5];
long long ans[maxn + 5];
int main() {
int Q;
scanf("%d%d", &n, &Q);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int c = ceil(1. * n / B2);
for (int i = 1; i <= c; i++) {
lp[i] = (i - 1) * B2 + 1;
rp[i] = min(n, i * B2);
}
for (int i = 1; i <= n; i++)
blg[i] = (i - 1) / B2 + 1;
for (int i = 1; i <= Q; i++) {
int m;
scanf("%d", &m);
seq[i].resize(m);
for (int j = 0; j < m; j++)
scanf("%d%d", &seq[i][j].first, &seq[i][j].second);
if (m > B1) {
int cnt = 0;
for (int j = 0; j < m; j++)
for (int k = seq[i][j].first; k <= seq[i][j].second; k++)
q1[++cnt] = {j, a[k]};
ans[i] = rude(cnt);
} else {
int cnt = 0;
for (int j = 0; j < m; j++) {
int l = seq[i][j].first, r = seq[i][j].second;
if (blg[l] == blg[r])
for (int k = l; k <= r; k++)
q1[++cnt] = {j, a[k]};
else {
for (int k = l; k <= rp[blg[l]]; k++)
q1[++cnt] = {j, a[k]};
for (int k = lp[blg[r]]; k <= r; k++)
q1[++cnt] = {j, a[k]};
}
}
ans[i] = rude(cnt);
for (int j = 0; j < m; j++) {
int bl1 = blg[seq[i][j].first], br1 = blg[seq[i][j].second] - 1;
if (bl1 >= br1)
continue;
q2[br1].push_back({i, j, 1});
q2[bl1].push_back({i, j, -1});
}
}
}
for (int i = 1; i <= c; i++) {
memset(sum, 0, sizeof(sum));
for (int j = 1; j <= rp[i]; j++)
sum[a[j]]++;
for (int j = 1; j <= n; j++)
sum[j] += sum[j - 1];
for (int j = 1; j <= n; j++) {
pre[j] = pre[j - 1];
if (j <= rp[i])
pre[j] += rp[i] - sum[a[j]];
else
pre[j] += sum[a[j] - 1];
}
for (auto q : q2[i]) {
int id = q.id, p = q.p, z = q.z;
int m = seq[id].size();
for (int j = 0; j < m; j++) {
if (j == p)
continue;
int l = seq[id][j].first, r = seq[id][j].second;
ans[id] += z * (pre[r] - pre[l - 1]);
int bl2 = blg[l] + 1, br2 = blg[r] - 1;
if (j > p && bl2 <= br2)
ans[id] -= z * (pre[rp[br2]] - pre[lp[bl2] - 1]);
}
}
}
for (int i = 1; i <= Q; i++)
printf("%lld\n", ans[i]);
}
|
