Submission #1244371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244371		Double_Slash	Diversity (CEOI21_diversity)	C++20	18 / 100	58 ms	6236 KiB

diversity

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;

const int SQRT = 547, MAX = 3e5;

int main() {
    int n, q;
    cin >> n >> q;
    int a[n];
    for (int &ai: a) cin >> ai;
    vector<array<int, 3>> qu(q);
    for (int i = q; i--;) {
        cin >> qu[i][0] >> qu[i][1];
        --qu[i][0], --qu[i][1];
        qu[i][2] = i;
    }
    sort(all(qu), [&] (auto &a, auto &b) { return a[0] / SQRT == b[0] / SQRT ? a[1] < b[1] : a[0] < b[0]; });
    int l = 0, r = -1, freq[MAX + 1]{n + 1}, ffreq[MAX + 1]{};
    vector<int> nxt(MAX + 1, -1), pre(MAX + 1, -1);
    auto p = [&] (int i, int j) {
        if (~i) nxt[i] = j;
        if (~j) pre[j] = i;
    };
    auto add = [&] (int i) {
        if (not ffreq[++freq[i = a[i]]]++) {
            p(freq[i], nxt[freq[i] - 1]);
            p(freq[i] - 1, freq[i]);
        }
        if (not --ffreq[freq[i] - 1]) p(pre[freq[i] - 1], freq[i]);
    };
    auto rem = [&] (int i) {
        if (not ffreq[--freq[i = a[i]]]++) {
            p(pre[freq[i] + 1], freq[i]);
            p(freq[i], freq[i] + 1);
        }
        if (not --ffreq[freq[i] + 1]) p(freq[i], nxt[freq[i] + 1]);
    };
    vector<ll> ans(q);
    ll squares[MAX + 1]{};
    for (int i = 1; i <= n; ++i) squares[i] = squares[i - 1] + (ll) i * (i + 1) / 2;
    for (auto &[li, ri, i]: qu) {
        while (r < ri) add(++r);
        while (r > ri) rem(r--);
        while (l > li) add(--l);
        while (l < li) rem(l++);
        vector<pint> raw, lhs, rhs;
        bool b = false;
        for (int f = 0; ~(f = nxt[f]);) raw.emplace_back(f, ffreq[f]);
        for (int j = raw.size(); j--;) {
            (b ? lhs : rhs).emplace_back(raw[j].first, (raw[j].second + 1) / 2);
            (b ? rhs : lhs).emplace_back(raw[j].first, raw[j].second / 2);
            b ^= raw[j].second & 1;
        }
        reverse(all(lhs));
        lhs.insert(lhs.end(), all(rhs));
        ll iw = 0;
        int sum = 0;
        for (auto &[f, cnt]: lhs) {
            if (not cnt) continue;
            ans[i] += (iw * cnt + sum * (ll) cnt * (cnt + 1) / 2) * f;
            if (cnt > 1) ans[i] += (ll) (cnt + 2) * (cnt - 1) / 2 * f * f;
            ans[i] += (ll) f * (f + 1) / 2 * cnt;
            iw += (ll) sum * cnt + (ll) f * cnt * (cnt + 1) / 2;
            sum += f * cnt;
        }
    }
    for (int i = q; i--;) cout << ans[i] << endl;
}

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