#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;
#define ff first
#define ss second
#define ll long long
const int MX = 3e5 + 5;
const int MX1 = 5e4 + 5;
const int B = 500;
int N, Q;
int a[MX], num[MX], l[MX], r[MX];
ll ans[MX1];
pair<pair<int, int>, pair<int, int> > q[MX1];
ll val;
struct T{
ll sum, left_sum, right_sum;
T() {
sum = left_sum = right_sum = 0;
}
} BIT[MX];
void update(int id, int l, int r, int pos, int x) {
if(l > pos || pos > r) return;
tree[id].sum += x;
tree[id].left_sum += x * (pos - l + 1);
tree[id].right_sum += x * (r - pos + 1);
if(l == r) return;
int mid = (l + r) / 2;
update(id * 2 + 1, l, mid, pos, x);
update(id * 2 + 2, mid + 1, r, pos, x);
}
T query(int id, int l, int r, int L, int R) {
T res;
if(L > r || l > R) return res;
if(L <= l && r <= R) return tree[id];
int mid = (l + r) / 2;
if(L > mid) return query(id * 2 + 2, mid + 1, r, L, R);
if(R <= mid) return query(id * 2 + 1, l, mid, L, R);
T x = query(id * 2 + 1, l, mid, L, R), y = query(id * 2 + 2, mid + 1, r, L, R);
res.sum = x.sum + y.sum;
res.left_sum = x.left_sum + y.left_sum + y.sum * (mid - L + 1);
res.right_sum = x.right_sum + y.right_sum + x.sum * (R - mid);
return res;
}
int prv(int x) {
if(x <= (N - 1) / 2) return N - x;
else return N - x - 1;
}
int nxt(int x) {
if(x <= N / 2) return N - x - 1;
else return N - x;
}
void add(int x) {
num[x]++;
l[num[x]] = r[num[x] - 1];
if(r[num[x]] == -1) r[num[x]] = l[num[x]];
if(r[num[x] - 1] == l[num[x] - 1]) r[num[x] - 1] = l[num[x] - 1] = -1;
else r[num[x] - 1] = prv(r[num[x] - 1]);
update(0, 0, N - 1, l[num[x]], 1);
T y, z;
if(l[num[x]] != 0) y = query(0, 0, N - 1, 0, l[num[x]] - 1);
if(l[num[x]] != N - 1) z = query(0, 0, N - 1, l[num[x]] + 1, N - 1);
val += y.right_sum + y.sum + z.left_sum + z.sum;
val += num[x];
}
void remove(int x) {
num[x]--;
r[num[x]] = l[num[x] + 1];
if(l[num[x]] == -1) l[num[x]] = r[num[x]];
if(r[num[x] + 1] == l[num[x] + 1]) r[num[x] + 1] = l[num[x] + 1] = -1;
else l[num[x] + 1] = nxt(l[num[x] + 1]);
update(0, 0, N - 1, r[num[x]], -1);
T y, z;
if(r[num[x]] != 0) y = query(0, 0, N - 1, 0, r[num[x]] - 1);
if(r[num[x]] != N - 1) z = query(0, 0, N - 1, r[num[x]] + 1, N - 1);
val -= y.right_sum + y.sum + z.left_sum + z.sum;
val -= (num[x] + 1);
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
memset(l, -1, sizeof(l));
memset(r, -1, sizeof(r));
cin >> N >> Q;
l[0] = 0;
r[0] = N / 2;
for(int i = 0; i < N; i++) cin >> a[i];
for(int i = 0; i < Q; i++) {
int l, r;
cin >> l >> r;
l--;
r--;
q[i] = {{l / B, r}, {l, i}};
}
sort(q, q + Q);
for(int i = 0; i < Q; i++) {
if(i == 0) {
for(int j = 0; j <= q[i].ff.ss; j++) add(a[j]);
for(int j = 0; j < q[i].ss.ff; j++) remove(a[j]);
ans[q[i].ss.ss] = val;
continue;
}
for(int j = q[i - 1].ff.ss + 1; j <= q[i].ff.ss; j++) add(a[j]);
for(int j = q[i - 1].ff.ss; j > q[i].ff.ss; j--) remove(a[j]);
for(int j = q[i - 1].ss.ff; j < q[i].ss.ff; j++) remove(a[j]);
for(int j = q[i - 1].ss.ff - 1; j >= q[i].ss.ff; j--) add(a[j]);
ans[q[i].ss.ss] = val;
}
for(int i = 0; i < Q; i++) {
cout << ans[i] << "\n";
}
}
Compilation message
diversity.cpp: In function 'void update(int, int, int, int, int)':
diversity.cpp:44:2: error: 'tree' was not declared in this scope; did you mean 'free'?
44 | tree[id].sum += x;
| ^~~~
| free
diversity.cpp: In function 'T query(int, int, int, int, int)':
diversity.cpp:56:30: error: 'tree' was not declared in this scope; did you mean 'free'?
56 | if(L <= l && r <= R) return tree[id];
| ^~~~
| free
