Submission #789759

#	Time	Username	Problem	Language	Result	Execution time	Memory
789759		math_rabbit_1028	Diversity (CEOI21_diversity)	C++14	64 / 100	7065 ms	4640 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q, b;
int arr[303030];
ll cnt[303030], ans = 0, res[50505];
pair<ll, ll> reord[2020];
map<int, ll> M;

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

ll sum[m + 1], xsum[m + 1];

void init(int p) {
    for (int i = 1; i <= m; i++) cnt[i] = 0;
    for (int i = Q[p].lt; i <= Q[p].rt; i++) cnt[arr[i]]++;
    M.clear();
    for (int i = 1; i <= m; i++) {
        auto iter = M.find(cnt[i]); int val = iter->second;
        if (iter == M.end()) M.insert({cnt[i], 1});
        else {
            M.erase(iter);
            M.insert({cnt[i], val + 1});
        }
    }
}

ll cal() {
    /*
    for (auto iter = M.rbegin(); iter != M.rend(); iter++) {
        cout << iter->first << " " << iter->second << "\n";
    }
    */

    int sz = M.size(), p = sz + 1, q = sz, tot = 0;
    for (auto iter = M.rbegin(); iter != M.rend(); iter++) {
        ll sm = (iter->second)/2, la = iter->second - sm;
        if (tot % 2 == 0) {
            if (sm > 0) reord[--p] = make_pair(iter->first, sm);
            reord[++q] = make_pair(iter->first, la);
        }
        else {
            reord[--p] = make_pair(iter->first, la);
            if (sm > 0) reord[++q] = make_pair(iter->first, sm);
        }
        tot += iter->second;
    }

    ll ret = 0, sum = 0, xsum = 0, s = 0;
    for (int i = p; i <= q; i++) {
        ll a = reord[i].first, k = reord[i].second;
        ret += k * a * (a + 1) / 2;
        ret += a * a * k * (k + 1) * (k + 2) / 6 - a * a * k;
        ret += a * k * (2 * s + k + 3) / 2 * sum;
        ret -= a * k * xsum;
        sum += a * k;
        xsum += a * k * (2 * s + k + 1) / 2;
        s += k;
        //cout << a << " " << k << " " << ret << "\n";
    }
    return ret;
}

void add(int i) {
    auto iter = M.find(cnt[i]); int val = iter->second;
    M.erase(iter);
    if (val > 1) M.insert({cnt[i], val - 1});

    cnt[i]++;

    iter = M.find(cnt[i]); val = iter->second;
    if (iter == M.end()) M.insert({cnt[i], 1});
    else {
        M.erase(iter);
        M.insert({cnt[i], val + 1});
    }
}

void rem(int i) {
    auto iter = M.find(cnt[i]); int val = iter->second;
    M.erase(iter);
    if (val > 1) M.insert({cnt[i], val - 1});

    cnt[i]--;

    iter = M.find(cnt[i]); val = iter->second;
    if (iter == M.end()) M.insert({cnt[i], 1});
    else {
        M.erase(iter);
        M.insert({cnt[i], val + 1});
    }
}

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);

    init(1);
    res[Q[1].idx] = cal();

    for (int i = 2; 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]);
        else for (int j = Q[i].rt + 1; j <= Q[i - 1].rt; j++) rem(arr[j]);

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

        res[Q[i].idx] = cal();
    }

    for (int i = 1; i <= q; i++) cout << res[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: 0 / 36