Submission #789626

#	Time	Username	Problem	Language	Result	Execution time	Memory
789626		math_rabbit_1028	Diversity (CEOI21_diversity)	C++14	64 / 100	7050 ms	142696 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], reord[303030], sum[303030], xsum[303030], ans = 0, res[50505];

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

struct seg {
    ll sum[4 * m], xsum[4 * m];
    void init(int v, int st, int ed) {
        if (st == ed) {
            sum[v] = reord[st];
            xsum[v] = (ll)st * reord[st];
            return;
        }
        int mid = (st + ed) / 2;
        init(2 * v, st, mid);
        init(2 * v + 1, mid + 1, ed);
        sum[v] = sum[2 * v] + sum[2 * v + 1];
        xsum[v] = xsum[2 * v] + xsum[2 * v + 1];
    }
    void update(int v, int st, int ed, int idx, ll diff) {
        if (st == idx && ed == idx) {
            sum[v] += diff;
            xsum[v] += (ll)st * diff;
            return;
        }
        if (idx < st || idx > ed) return;
        int mid = (st + ed) / 2;
        update(2 * v, st, mid, idx, diff);
        update(2 * v + 1, mid + 1, ed, idx, diff);
        sum[v] = sum[2 * v] + sum[2 * v + 1];
        xsum[v] = xsum[2 * v] + xsum[2 * v + 1];
    }
    ll getsum(int v, int st, int ed, int lt, int rt) {
        if (ed < lt || st > rt) return 0;
        if (lt <= st && ed <= rt) return sum[v];
        int mid = (st + ed) / 2;
        return getsum(2 * v, st, mid, lt, rt) + getsum(2 * v + 1, mid + 1, ed, lt, rt);
    }
    ll getxsum(int v, int st, int ed, int lt, int rt) {
        if (ed < lt || st > rt) return 0;
        if (lt <= st && ed <= rt) return xsum[v];
        int mid = (st + ed) / 2;
        return getxsum(2 * v, st, mid, lt, rt) + getxsum(2 * v + 1, mid + 1, ed, lt, rt);
    }
} s;

void init(int p) {
    for (int i = 1; i <= m; i++) cnt[i] = 0;
    ans = 0;

    for (int i = Q[p].lt; i <= Q[p].rt; i++) cnt[arr[i]]++;
    for (int i = 1; i <= m; i++) cnt2[cnt[i]]++;

    vector<int> v;
    v.push_back(0);
    for (int i = 0; i <= n; i++) {
        for (int j = 1; j <= cnt2[i]; j++) v.push_back(i);
    }

    for (int i = 1; i <= m/2; i++) {
        reord[i] = v[2 * i - 1];
    }
    for (int i = 1; i <= m/2; i++) {
        reord[m - i + 1] = v[2 * i];
    }

    for (ll i = 1; i <= m; i++) {
        ans += reord[i] * (reord[i] + 1) / 2;
        sum[i] = sum[i - 1] + reord[i];
        xsum[i] = xsum[i - 1] + i * reord[i];
    }

    for (ll i = 1; i <= m; i++) {
        ans += reord[i] * ((i + 1) * sum[i - 1] - xsum[i - 1]);
    }
}

void add(int j) {
    int idx, i;
    idx = upper_bound(cnt2 + 1, cnt2 + m + 1, cnt[arr[j]]) - cnt2 - 1;
    cnt[arr[j]]++;
    cnt2[idx]++;
    if (idx % 2 == 0) i = m - idx/2 + 1;
    else i = (idx + 1) / 2;
    reord[i]++;
    ans += reord[i];
    ans += (i + 1) * s.getsum(1, 1, m, 1, i - 1) - s.getxsum(1, 1, m, 1, i - 1);
    ans += s.getxsum(1, 1, m, i + 1, m) - (i - 1) * s.getsum(1, 1, m, i + 1, m);
    s.update(1, 1, m, i, 1);
}

void rem(int j) {
    int idx, i;
    idx = lower_bound(cnt2 + 1, cnt2 + m + 1, cnt[arr[j]]) - cnt2;
    cnt[arr[j]]--;
    cnt2[idx]--;
    if (idx % 2 == 0) i = m - idx/2 + 1;
    else i = (idx + 1) / 2;
    reord[i]--;
    ans -= reord[i] + 1;
    ans -= (i + 1) * s.getsum(1, 1, m, 1, i - 1) - s.getxsum(1, 1, m, 1, i - 1);
    ans -= s.getxsum(1, 1, m, i + 1, m) - (i - 1) * s.getsum(1, 1, m, i + 1, m);
    s.update(1, 1, m, i, -1);
}

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

    cin >> n >> q; b = 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);

    int p = 1;
    for (int i = 0; i <= n/b; i++) {
        if (Q[p].lt/b != i) continue;

        init(p);
        res[Q[p].idx] = ans;

        p++;
        while (p <= q && Q[p].lt/b == i) {
            for (int j = Q[p - 1].rt + 1; j <= Q[p].rt; j++) add(j);
            if (Q[p - 1].lt > Q[p].lt) for (int j = Q[p].lt; j < Q[p - 1].lt; j++) add(j);
            else for (int j = Q[p - 1].lt; j < Q[p].lt; j++) rem(j);
            res[Q[p].idx] = ans;
            p++;
        }
    }

    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