#pragma GCC optimize("O3, unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct SmartFenwick {
vector<ll> k, b;
int n{};
void init(int x) {
n = x;
k.resize(x + 1), b.resize(x + 1);
}
inline void addk(int i, ll v) {
for (int x = i + 1; x <= n; x += x & -x) {
k[x] += v;
}
}
inline void addb(int i, ll v) {
for (int x = i + 1; x <= n; x += x & -x) {
b[x] += v;
}
}
inline void rangeAdd(int l, int r, ll v) {
addk(r, -v);
addb(r, (r - 1) * v);
}
inline ll sum(int i) {
ll K = 0, B = 0;
for (int x = i + 1; x > 0; x -= x & -x) {
K += k[x], B += b[x];
}
return B + K * i;
}
inline ll rangeSum(int l, int r) {
return sum(r - 1) - sum(l - 1);
}
} t[2][2]; // (left/right), (L/R)
struct Query {
int l, r, block, idx;
bool operator<(Query oth) const {
if (oth.block != block) {
return block < oth.block;
}
return (block & 1) ? r > oth.r : r < oth.r;
}
};
constexpr int B = 1400;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> yy = a;
sort(yy.begin(), yy.end());
yy.resize(unique(yy.begin(), yy.end()) - yy.begin());
for (int &x : a) {
x = lower_bound(yy.begin(), yy.end(), x) - yy.begin();
}
const int m = yy.size();
vector<Query> queries(q);
vector<ll> answer(q);
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
l -= 1;
queries[i].l = l, queries[i].r = r, queries[i].block = l / B, queries[i].idx = i;
}
sort(queries.begin(), queries.end());
vector<int> head(n + 1);
for (int i = 1; i <= n; ++i) {
head[i] = m;
}
vector<int> pos(m), cnt(m), ord(m);
iota(pos.begin(), pos.end(), 0);
ord = pos;
int siz[2]{(m + 1) / 2, m / 2};
t[0][0].init(siz[0]);
t[0][1].init(siz[0]);
t[1][0].init(siz[1]);
t[1][1].init(siz[1]);
ll ans = 0;
int len = 0;
auto eval = [&](int i) {
return 1LL * cnt[i] * (len - cnt[i]) + 1LL * (cnt[i] + 1) * cnt[i] / 2;
};
auto modify = [&](int i, int x) {
ans += x * len;
len += x;
ans -= eval(i);
int p = pos[i];
int start = (x == -1 ? head[cnt[i]] : head[cnt[i] + 1] - 1);
if (p != start) {
int id = ord[start];
pos[id] = p;
ord[p] = id;
pos[i] = start;
ord[start] = i;
p = start;
}
int side = p % 2;
int s = p / 2;
ans += x * t[side][side ^ 1].rangeSum(s + 1, siz[side]);
t[side][side].rangeAdd(s + 1, siz[side], x);
t[side][side ^ 1].rangeAdd(0, s, x);
ans += x * t[side][side].rangeSum(0, s);
ans += x * t[side ^ 1][side ^ 1].rangeSum(0, siz[side ^ 1]);
t[side ^ 1][side].rangeAdd(0, siz[side ^ 1], x);
if (x == -1) {
head[cnt[i]] = p + 1;
cnt[i] -= 1;
} else {
cnt[i] += 1;
head[cnt[i]] = p;
}
ans += eval(i);
};
int lx = 0, rx = 0;
for (auto [l, r, bl, i] : queries) {
while (rx < r) {
modify(a[rx++], 1);
}
while (lx > l) {
modify(a[--lx], 1);
}
while (lx < l) {
modify(a[lx++], -1);
}
while (rx > r) {
modify(a[--rx], -1);
}
answer[i] = ans;
}
for (int i = 0; i < q; ++i) {
cout << answer[i] << '\n';
}
return 0;
}
Compilation message
diversity.cpp:1:40: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
1 | #pragma GCC optimize("O3, unroll-loops")
| ^
diversity.cpp:12:20: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
12 | void init(int x) {
| ^
diversity.cpp:17:33: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
17 | inline void addk(int i, ll v) {
| ^
diversity.cpp:23:33: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
23 | inline void addb(int i, ll v) {
| ^
diversity.cpp:29:44: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
29 | inline void rangeAdd(int l, int r, ll v) {
| ^
diversity.cpp:34:24: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
34 | inline ll sum(int i) {
| ^
diversity.cpp:44:36: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
44 | inline ll rangeSum(int l, int r) {
| ^
diversity.cpp:52:31: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
52 | bool operator<(Query oth) const {
| ^~~~~
diversity.cpp:63:10: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
63 | int main() {
| ^
diversity.cpp: In function 'int main()':
diversity.cpp:120:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
120 | auto eval = [&](int i) {
| ^
diversity.cpp:124:35: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
124 | auto modify = [&](int i, int x) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
