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
| #include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define maxn 100010
#define maxs 340
#define lowbit(i) ((i) & (-i))
#define ll long long
using namespace std;
int n, m, a[maxn];
ll pre[maxn], suf[maxn];
int b[maxn], cnt;
void init_hash() {
for (int i = 1; i <= n; ++i) b[i] = a[i];
sort(b + 1, b + n + 1); cnt = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
}
int Bit[maxn];
void add(int i, int v) { while (i <= cnt) Bit[i] += v, i += lowbit(i); }
int get_sum(int i) {
int s = 0;
while (i) s += Bit[i], i -= lowbit(i);
return s;
}
int blo;
struct Query {
int l, r, id;
friend bool operator < (const Query &u, const Query &v) {
return u.l / blo == v.l / blo ? u.r < v.r : u.l < v.l;
}
} Q[maxn];
struct query {
int l, r, opt, id;
}; vector<query> A[maxn], B[maxn];
struct Block {
int n, blo, num, l[maxs], r[maxs], bl[maxn], a[maxn], d[maxs];
void init(int _n) {
n = _n; blo = sqrt(n); num = (n + blo - 1) / blo;
for (int i = 1; i <= num; ++i) {
l[i] = (i - 1) * blo + 1;
r[i] = i * blo;
} r[num] = n;
for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1;
for (int i = 1; i <= n; ++i) a[i] = 0;
for (int i = 1; i <= num; ++i) d[i] = 0;
}
void update(int k, int v) {
for (int i = k; i <= r[bl[k]]; ++i) a[i] += v;
for (int i = bl[k] + 1; i <= num; ++i) d[i] += v;
}
int query(int k) { return d[bl[k]] + a[k]; }
} S;
ll ans[maxn];
void solve() {
S.init(cnt);
for (int i = 1; i <= n; ++i) {
S.update(a[i], 1);
for (auto t : A[i])
for (int j = t.l; j <= t.r; ++j)
ans[t.id] += t.opt * (i - S.query(a[j]));
}
S.init(cnt);
for (int i = n; i; --i) {
S.update(a[i], 1);
for (auto t : B[i])
for (int j = t.l; j <= t.r; ++j)
ans[t.id] += t.opt * S.query(a[j] - 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m; blo = sqrt(m);
for (int i = 1; i <= n; ++i) cin >> a[i]; init_hash();
for (int i = 1; i <= n; ++i) add(a[i], 1), pre[i] = pre[i - 1] + i - get_sum(a[i]);
for (int i = 1; i <= cnt; ++i) Bit[i] = 0;
for (int i = n; i; --i) add(a[i], 1), suf[i] = suf[i + 1] + get_sum(a[i] - 1);
for (int i = 1; i <= m; ++i) cin >> Q[i].l >> Q[i].r, Q[i].id = i;
sort(Q + 1, Q + m + 1); int l = Q[1].l, r = l - 1;
for (int i = 1; i <= m; ++i) {
if (r < Q[i].r) {
ans[Q[i].id] += pre[Q[i].r] - pre[r];
A[l - 1].push_back({ r + 1, Q[i].r, -1, Q[i].id });
r = Q[i].r;
}
if (l > Q[i].l) {
ans[Q[i].id] += suf[Q[i].l] - suf[l];
B[r + 1].push_back({ Q[i].l, l - 1, -1, Q[i].id });
l = Q[i].l;
}
if (r > Q[i].r) {
ans[Q[i].id] -= pre[r] - pre[Q[i].r];
A[l - 1].push_back({ Q[i].r + 1, r, 1, Q[i].id });
r = Q[i].r;
}
if (l < Q[i].l) {
ans[Q[i].id] -= suf[l] - suf[Q[i].l];
B[r + 1].push_back({ l, Q[i].l - 1, 1, Q[i].id });
l = Q[i].l;
}
} solve();
for (int i = 1; i <= m; ++i) ans[Q[i].id] += ans[Q[i - 1].id];
for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
return 0;
}
|