Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
The value of a subarray does not care about the order of elements inside it. It only cares about frequencies: for each value , its contribution is .
Suppose the current subarray already has copies of value . If you add one more , only one term changes:
So adding/removing one endpoint can update the answer in .
Answering queries independently is too slow. But if two queries have close endpoints, you can move from one interval to the other by adding/removing only a few elements.
This is exactly what Mo's algorithm is for: sort queries by blocks of , and inside each block by . Maintain a sliding current interval and update it until it matches the next query.
Use block size about . Maintain cnt[x] and cur:
cur += (2*cnt[x] + 1) * x, then cnt[x]++cur -= (2*cnt[x] - 1) * x, then cnt[x]--Store answers by original query index. Use long long, because the answer can be around .
For an interval, the power is
where is the frequency of value inside the current interval.
So the whole problem is frequency maintenance. No fancy segment tree magic needed; trying to force one here is how you end up debugging sadness at 3 AM.
If the current count of value is , then its contribution is .
When we add one occurrence of , the count becomes , so the answer changes by
When we remove one occurrence of , the count becomes , so the answer changes by
Thus we can add or remove an endpoint in .
We have up to queries. Processing each query from scratch is obviously dead:
which is Codeforces' way of saying “nope”.
Instead, sort the queries using Mo's order:
A common optimization is alternating the order of between blocks:
This reduces pointer thrashing. Not theoretically magical, just a very good constant-factor trick.
Maintain a current interval . Initially it is empty, say , using -indexed arrays.
For each sorted query , move the pointers:
--L++RL++R--After that, the maintained value cur is exactly the answer for this query.
We maintain the invariant:
for the current interval .
Initially the interval is empty, all counts are , and cur = 0, so the invariant holds.
When adding a value with old count , only the contribution of changes. The update
changes into , so the invariant remains true.
When removing a value with old count , again only changes. The update
changes into , so the invariant remains true.
Mo's algorithm moves from one queried interval to another using exactly these add/remove operations. Therefore, once the current interval equals a query interval, cur equals that query's power.
With block size , Mo's ordering gives about
pointer moves, each handled in .
Memory usage is
where is the maximum possible array value.
Use long long: the answer can be as large as
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Query {
int l, r, idx;
};
int main() {
setIO();
int n, t;
cin >> n >> t;
vector<int> a(n);
for (int &x : a) cin >> x;
vector<Query> queries(t);
for (int i = 0; i < t; i++) {
int l, r;
cin >> l >> r;
--l, --r;
queries[i] = {l, r, i};
}
int block = max(1, (int)sqrt(n));
sort(queries.begin(), queries.end(), [&](const Query &x, const Query &y) {
int bx = x.l / block;
int by = y.l / block;
if (bx != by) return bx < by;
if (bx & 1) return x.r > y.r;
return x.r < y.r;
});
vector<int> cnt(1000001, 0);
vector<ll> ans(t);
ll cur = 0;
int L = 0, R = -1;
auto add = [&](int pos) {
int x = a[pos];
cur += (2LL * cnt[x] + 1) * x;
cnt[x]++;
};
auto remove = [&](int pos) {
int x = a[pos];
cur -= (2LL * cnt[x] - 1) * x;
cnt[x]--;
};
for (const Query &q : queries) {
while (L > q.l) add(--L);
while (R < q.r) add(++R);
while (L < q.l) remove(L++);
while (R > q.r) remove(R--);
ans[q.idx] = cur;
}
for (ll x : ans) {
cout << x << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Query {
int l, r, idx;
};
int main() {
setIO();
int n, t;
cin >> n >> t;
vector<int> a(n);
for (int &x : a) cin >> x;
vector<Query> queries(t);
for (int i = 0; i < t; i++) {
int l, r;
cin >> l >> r;
--l, --r;
queries[i] = {l, r, i};
}
int block = max(1, (int)sqrt(n));
sort(queries.begin(), queries.end(), [&](const Query &x, const Query &y) {
int bx = x.l / block;
int by = y.l / block;
if (bx != by) return bx < by;
if (bx & 1) return x.r > y.r;
return x.r < y.r;
});
vector<int> cnt(1000001, 0);
vector<ll> ans(t);
ll cur = 0;
int L = 0, R = -1;
auto add = [&](int pos) {
int x = a[pos];
cur += (2LL * cnt[x] + 1) * x;
cnt[x]++;
};
auto remove = [&](int pos) {
int x = a[pos];
cur -= (2LL * cnt[x] - 1) * x;
cnt[x]--;
};
for (const Query &q : queries) {
while (L > q.l) add(--L);
while (R < q.r) add(++R);
while (L < q.l) remove(L++);
while (R > q.r) remove(R--);
ans[q.idx] = cur;
}
for (ll x : ans) {
cout << x << '\n';
}
return 0;
}