86DUnreviewed2200GPT-5.5 (high)

Powerful array

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

data structures implementation math two pointers

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

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 $s$ , its contribution is $K_s^2 \cdot s$ .

Suppose the current subarray already has $c$ copies of value $x$ . If you add one more $x$ , only one term changes:

(c+1)^2x - c^2x = (2c+1)x.

So adding/removing one endpoint can update the answer in $O(1)$ .

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 $l$ , and inside each block by $r$ . Maintain a sliding current interval $[L,R]$ and update it until it matches the next query.

Use block size about $\sqrt n$ . Maintain cnt[x] and cur:

add value $x$ : cur += (2*cnt[x] + 1) * x, then cnt[x]++
remove value $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 $4\cdot 10^{16}$ .

Key observation

For an interval, the power is

\sum_s K_s^2 \cdot s,

where $K_s$ is the frequency of value $s$ 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 $x$ is $c$ , then its contribution is $c^2x$ .

When we add one occurrence of $x$ , the count becomes $c+1$ , so the answer changes by

(c+1)^2x - c^2x = (2c+1)x.

When we remove one occurrence of $x$ , the count becomes $c-1$ , so the answer changes by

(c-1)^2x - c^2x = -(2c-1)x.

Thus we can add or remove an endpoint in $O(1)$ .

Offline queries with Mo's algorithm

We have up to $2\cdot 10^5$ queries. Processing each query from scratch is obviously dead:

O(nt)

which is Codeforces' way of saying “nope”.

Instead, sort the queries using Mo's order:

Split positions into blocks of size about $\sqrt n$ .
Sort by block of $l$ .
Inside the same block, sort by $r$ .

A common optimization is alternating the order of $r$ between blocks:

even block: increasing $r$
odd block: decreasing $r$

This reduces pointer thrashing. Not theoretically magical, just a very good constant-factor trick.

Maintain a current interval $[L,R]$ . Initially it is empty, say $L=0$ , $R=-1$ using $0$ -indexed arrays.

For each sorted query $[l,r]$ , move the pointers:

while $L > l$ , add --L
while $R < r$ , add ++R
while $L < l$ , remove L++
while $R > r$ , remove R--

After that, the maintained value cur is exactly the answer for this query.

Correctness

We maintain the invariant:

\texttt{cur} = \sum_s \texttt{cnt}[s]^2 \cdot s

for the current interval $[L,R]$ .

Initially the interval is empty, all counts are $0$ , and cur = 0, so the invariant holds.

When adding a value $x$ with old count $c$ , only the contribution of $x$ changes. The update

\texttt{cur} \mathrel{+}= (2c+1)x

changes $c^2x$ into $(c+1)^2x$ , so the invariant remains true.

When removing a value $x$ with old count $c$ , again only $x$ changes. The update

\texttt{cur} \mathrel{-}= (2c-1)x

changes $c^2x$ into $(c-1)^2x$ , 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.

Complexity

With block size $B \approx \sqrt n$ , Mo's ordering gives about

O((n+t)\sqrt n)

pointer moves, each handled in $O(1)$ .

Memory usage is

O(n + A + t),

where $A \le 10^6$ is the maximum possible array value.

Use long long: the answer can be as large as

(2\cdot 10^5)^2 \cdot 10^6 = 4\cdot 10^{16}.

#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;
}

View on Codeforces Back to the list