#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;
int N, Q, B;
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;
}
} tree[4 * MX];
void show(T x) {
cout << x.left_sum << " " << x.right_sum << " " << x.sum << "\n";
}
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];
// show(y);
// show(z);
// cout << val << "\n---------\n";
}
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;
B = sqrt(Q) * N / 2;
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;a#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;
int N, Q, B;
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;
}
} tree[4 * MX];
void show(T x) {
cout << x.left_sum << " " << x.right_sum << " " << x.sum << "\n";
}
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];
// show(y);
// show(z);
// cout << val << "\n---------\n";
}
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;
B = N / 2 / sqrt(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";
}
}
}
for(int i = 0; i < Q; i++) {
cout << ans[i] << "\n";
}
}
Compilation message
diversity.cpp:139:26: error: stray '#' in program
139 | ans[q[i].ss.ss] = val;a#include <algorithm>
| ^
diversity.cpp: In function 'int main()':
diversity.cpp:139:26: error: expected ';' before 'include'
139 | ans[q[i].ss.ss] = val;a#include <algorithm>
| ^~~~~~~~
| ;
diversity.cpp:139:25: warning: statement has no effect [-Wunused-value]
139 | ans[q[i].ss.ss] = val;a#include <algorithm>
| ^
diversity.cpp:179:16: error: a function-definition is not allowed here before '{' token
179 | void show(T x) {
| ^
diversity.cpp:183:51: error: a function-definition is not allowed here before '{' token
183 | void update(int id, int l, int r, int pos, int x) {
| ^
diversity.cpp:194:45: error: a function-definition is not allowed here before '{' token
194 | T query(int id, int l, int r, int L, int R) {
| ^
diversity.cpp:208:16: error: a function-definition is not allowed here before '{' token
208 | int prv(int x) {
| ^
diversity.cpp:213:16: error: a function-definition is not allowed here before '{' token
213 | int nxt(int x) {
| ^
diversity.cpp:218:17: error: a function-definition is not allowed here before '{' token
218 | void add(int x) {
| ^
diversity.cpp:235:20: error: a function-definition is not allowed here before '{' token
235 | void remove(int x) {
| ^
diversity.cpp:249:12: error: a function-definition is not allowed here before '{' token
249 | int main() {
| ^
diversity.cpp:166:5: warning: unused variable 'N' [-Wunused-variable]
166 | int N, Q, B;
| ^
diversity.cpp:166:8: warning: unused variable 'Q' [-Wunused-variable]
166 | int N, Q, B;
| ^
diversity.cpp:166:11: warning: unused variable 'B' [-Wunused-variable]
166 | int N, Q, B;
| ^
diversity.cpp:167:5: warning: unused variable 'a' [-Wunused-variable]
167 | int a[MX], num[MX], l[MX], r[MX];
| ^
diversity.cpp:167:12: warning: unused variable 'num' [-Wunused-variable]
167 | int a[MX], num[MX], l[MX], r[MX];
| ^~~
diversity.cpp:167:21: warning: unused variable 'l' [-Wunused-variable]
167 | int a[MX], num[MX], l[MX], r[MX];
| ^
diversity.cpp:167:28: warning: unused variable 'r' [-Wunused-variable]
167 | int a[MX], num[MX], l[MX], r[MX];
| ^
diversity.cpp:168:4: warning: unused variable 'ans' [-Wunused-variable]
168 | ll ans[MX1];
| ^~~
diversity.cpp:169:39: warning: unused variable 'q' [-Wunused-variable]
169 | pair<pair<int, int>, pair<int, int> > q[MX1];
| ^
diversity.cpp:170:4: warning: unused variable 'val' [-Wunused-variable]
170 | ll val;
| ^~~
diversity.cpp:177:3: warning: unused variable 'tree' [-Wunused-variable]
177 | } tree[4 * MX];
| ^~~~
