Submission #789765

#	Time	Username	Problem	Language	Result	Execution time	Memory
789765		math_rabbit_1028	Diversity (CEOI21_diversity)	C++14	100 / 100	6200 ms	6000 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q, b;
int arr[303030];
ll cnt[303030], cnt2[303030], sum[303030], xsum[303030], ans[50505];
pair<ll, ll> reord[303030];
unordered_set<int> S;

const int m = 300000;

struct query{
    int idx, lt, rt;
} Q[50505];

bool compare(query p, query q) {
    if (p.lt/b == q.lt/b) return p.rt < q.rt;
    return (p.lt/b) < (q.lt/b);
}

void add(int i, int diff) {
    if (cnt2[cnt[i]] == 1) S.erase(cnt[i]);
    cnt2[cnt[i]]--;
    cnt[i] += diff;
    if (cnt2[cnt[i]] == 0) S.insert(cnt[i]);
    cnt2[cnt[i]]++;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q; b = (int)sqrt(n);
    for (int i = 1; i <= n; i++) cin >> arr[i];

    for (int i = 1; i <= q; i++) cin >> Q[i].lt >> Q[i].rt;
    for (int i = 1; i <= q; i++) Q[i].idx = i;

    sort(Q + 1, Q + q + 1, compare);

    Q[0].lt = 1; Q[0].rt = 0;
    for (int i = 1; i <= q; i++) {
        if (Q[i - 1].rt < Q[i].rt) for (int j = Q[i - 1].rt + 1; j <= Q[i].rt; j++) add(arr[j], 1);
        else for (int j = Q[i].rt + 1; j <= Q[i - 1].rt; j++) add(arr[j], -1);

        if (Q[i - 1].lt > Q[i].lt) for (int j = Q[i].lt; j < Q[i - 1].lt; j++) add(arr[j], 1);
        else for (int j = Q[i - 1].lt; j < Q[i].lt; j++) add(arr[j], -1);

        vector< pair<int, ll> > v;
        for (auto iter = S.begin(); iter != S.end(); iter++) {
            v.emplace_back(*iter, cnt2[*iter]);
        }

        sort(v.begin(), v.end());

        int sz = v.size(), tot = 0;
        for (int i = sz - 1; i >= 0; i--) {
            ll sm = (v[i].second)/2, la = v[i].second - sm;
            if (tot & 1) {
                reord[i + 1] = make_pair(v[i].first, sm);
                reord[sz * 2 - i] = make_pair(v[i].first, la);
            }
            else {
                reord[i + 1] = make_pair(v[i].first, la);
                reord[sz * 2 - i] = make_pair(v[i].first, sm);
            }
            tot += v[i].second;
        }

        ll res = 0, sum = 0, xsum = 0, s = 0;
        for (int i = 1; i <= sz * 2; i++) {
            ll a = reord[i].first, k = reord[i].second;
            res = res
                + k * a * (a + 1) / 2
                + a * a * k * (k + 1) * (k + 2) / 6 - a * a * k
                + a * k * (2 * s + k + 3) / 2 * sum
                - a * k * xsum;
            sum = sum + a * k;
            xsum = xsum + a * k * (2 * s + k + 1) / 2;
            s = s + k;
        }
        ans[Q[i].idx] = res;
    }

    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 26 / 26
• Subtask 6: 36 / 36