#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int nmax = 3e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, q;
int absol(int x) { return (x >= 0? x : -x);}
namespace Treap {
struct Node {
Node *l, *r;
int area, pri;
int ind() { return l -> area + 1; }
int val, sum;
bool lazy;
ll intl, intr; // left : e mai mic in left
}*nil = new Node{0, 0, 0, -1, 0, 0, 0, 0, 0};
using ns = Node*;
struct pns { ns l, r; };
ns updnode(ns node, ns x, int w) {
(w == 1? node -> r : node -> l) = x;
node -> area = 1 + node -> l -> area + node -> r -> area;
node -> sum = node -> val + node -> l -> val + node -> r -> val;
node -> intl = node -> l -> intl + (ll)(node -> r -> sum + node -> val) * (node -> ind()) + node -> r -> intl;
node -> intr = node -> r -> intr + (ll)(node -> l -> sum + node -> val) * (node -> r -> area + 1) + node -> l -> intr;
return node;
}
void prop(ns node) {
if(node == nil)
return;
if(node -> lazy == 1) {
swap(node -> l, node -> r);
swap(node -> intl, node -> intr);
node -> l -> lazy ^= 1;
node -> r -> lazy ^= 1;
node -> lazy = 0;
}
return;
}
pns split(ns node, int val) {
prop(node);
pns temp;
return node == nil? pns{nil, nil}:
node -> area <= val? pns{node, nil}:
val == 0? pns{nil, node}:
node -> ind() <= val? (temp = split(node -> r, val - node ->ind()), temp.l = updnode(node, temp.l, 1), temp):
(temp = split(node -> l, val), temp.r = updnode(node, temp.r, 0), temp);
}
ns merge(ns l, ns r) {
prop(l);
prop(r);
return l == nil? r:
r == nil? l:
l -> pri < r -> pri? updnode(r, merge(l, r -> l), 0):
updnode(l, merge(l -> r, r), 1);
}
ns parity[2] = {nil, nil};
void flip(ns& root) {
root -> lazy ^= 1;
prop(root);
}
void append(ns& root) { root = merge(new Node{nil, nil, 1, absol(rng()), 0, 0, 0, 0, 0}, root); }
void pop(ns& root) { pns temp = split(root, 1); root = temp.r; }
ll modify(ns& root, int poz, int with) {
//cerr << poz << ' ';
int how = (root == parity[0]? 1 : 0);
poz++;
pns temp[2];
temp[0] = split(root, poz - 1);
temp[1] = split(temp[0].r, 1);
temp[1].l -> val += with;
temp[1].l -> sum += with;
temp[1].l -> intl += with;
temp[1].l -> intr += with;
ll modifier = temp[1].r -> intl + temp[0].l -> intr;
root = merge(temp[0].l, merge(temp[1].l, temp[1].r));
poz = root -> area - poz;
if(how == 1) modifier += parity[how] -> intl;
else modifier += parity[how] -> intr;
//cerr << "> " << modifier << '\n';
modifier += (ll)parity[how] -> sum * poz;
//cerr << how << ' ' << parity[how] -> sum<< '/' << parity[how] -> area << ' ' << root -> area << ' ' << poz << '\n';
//cerr << modifier << '\n';
modifier *= with;
return modifier;
}
}
using namespace Treap;
int buck;
int v[nmax];
struct Query {
int l, r, ind;
bool operator <(const Query& other) const {
return (l / buck < other.l / buck || (l / buck == other.l / buck && r < other.r));
}
};
namespace Mo {
deque<int> sorted;
deque<int> vals;
int freq[nmax];
int atrindex[nmax];
ll total, comb, sum, sqsum;
void add(int x) {
x = v[x];
//cerr <<x << '\n';
int it;
if(freq[x] == 0) {
flip(parity[0]);
flip(parity[1]);
swap(parity[0], parity[1]);
append(parity[0]);
it = 0;
atrindex[x] = sorted.size();
sorted.push_front(0);
vals.push_front(x);
}
else {
it = prev(upper_bound(sorted.begin(), sorted.end(), sorted.rbegin()[atrindex[x]])) - sorted.begin();
swap(atrindex[x], atrindex[vals[it]]);
}
total += modify(parity[it % 2], it / 2, 1);
sorted[it]++;
sqsum += freq[x] * 2 + 1;
sum++;
freq[x]++;
comb += freq[x];
//cerr << parity[0] -> area << ' ' << parity[1] -> area << '\n';
}
void erase(int x) {
x = v[x];
int it;
it = lower_bound(sorted.begin(), sorted.end(), sorted.rbegin()[atrindex[x]]) - sorted.begin();
swap(atrindex[x], atrindex[vals[it]]);
swap(vals.rbegin()[atrindex[x]], vals.rbegin()[atrindex[vals[it]]]);
total += modify(parity[it % 2], it / 2, -1);
sorted[it]--;
comb -= freq[x];
freq[x]--;
sum--;
sqsum -= freq[x] * 2 + 1;
if(freq[x] == 0) {
pop(parity[0]);
flip(parity[0]);
flip(parity[1]);
swap(parity[0], parity[1]);
sorted.pop_back();
vals.pop_back();
}
return;
}
ll query() {
//cerr << total << ' ' << freq[1] << ' ' << comb << ' ' << sum << ' ' << sqsum << '\n';
return total + comb + (sum * sum - sqsum) / 2;
}
}
int main() {
cin >> n >> q;
buck = max(1.0, sqrt((ll) n * n / q));
for(int i = 1; i <= n; i++)
cin >> v[i];
vector<int> rez(q);
vector<Query> qs(q);
int cnt = 0;
for(auto &[l, r, ind] : qs) {
cin >> l >> r;
ind = cnt++;
}
sort(qs.begin(), qs.end());
int lastl = 1, lastr = 0;
for(auto [l, r, ind] : qs) {
//cerr << l << ' ' << r << ' ' << ind << '\n';0
while(lastr < r)
Mo::add(++lastr);
while(lastl > l)
Mo::add(--lastl);
while(lastl < l)
Mo::erase(lastl++);
while(lastr > r)
Mo::erase(lastr--);
//cerr << lastr << ' ' << lastl << '\n';
//for(auto x : Mo::sorted)
//cerr << x << ' ';
//cerr << '\n';
//for(auto x : Mo::vals)
//cerr << x << ' ';
//cerr << '\n';
rez[ind] = Mo::query();
}
//cerr << "unamog\n";
for(auto x : rez)
cout << x << '\n';
}
Compilation message
diversity.cpp: In function 'int main()':
diversity.cpp:180:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
180 | for(auto &[l, r, ind] : qs) {
| ^
diversity.cpp:187:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
187 | for(auto [l, r, ind] : qs) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
320 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
320 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
320 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
