Submission #613684

#	Time	Username	Problem	Language	Result	Execution time	Memory
613684		yuto1115	Diversity (CEOI21_diversity)	C++17	100 / 100	1245 ms	8056 KiB

diversity

#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; --i)
#define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int sz = 300000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vi a(n);
    for (int &i: a) {
        cin >> i;
        --i;
    }
    vi l(q), r(q);
    rep(i, q) {
        cin >> l[i] >> r[i];
        --l[i];
    }
    const int B = 1338;
    vi ord(q);
    iota(all(ord), 0);
    sort(all(ord), [&](int i, int j) {
        if (r[i] / B != r[j] / B) return r[i] / B < r[j] / B;
        return l[i] < l[j];
    });
    vi cnt(sz);
    vi mp(n + 1);
    auto add = [&](int x) {
        --mp[cnt[x]];
        ++mp[++cnt[x]];
    };
    auto del = [&](int x) {
        --mp[cnt[x]];
        ++mp[--cnt[x]];
    };
    auto calc = [&](int s, int a, int k, int n) -> ll {
        assert(a > 0 and k > 0 and s + a * k <= n / 2);
        ll res = 0;
        res -= (ll) k * (k + 1) * (2 * k + 1) / 6 * a * a;
        res += (ll) k * (k + 1) / 2 * a * (n - 2 * s);
        res += (ll) k * s * (n - s);
        return res;
    };
    const int D = min(550, n + 1);
    vi can;
    {
        vi v(sz);
        rep(i, n) ++v[a[i]];
        rep(i, sz) if (v[i] >= D) can.pb(i);
    }
    auto solve = [&mp, &calc, &D, &can, &cnt](int n) -> ll {
        vp ls;
        rep2(i, 1, D) if (mp[i]) ls.eb(i, mp[i]);
        for (int i: can) if (cnt[i] >= D) ls.eb(cnt[i], 1);
        sort(all(ls));
        --ls.back().second;
        vi v(2);
        ll res = 0;
        for (auto[f, s]: ls) {
            if (!f or !s) continue;
//            cerr << f << ' ' << s << endl;
            if (v[0] > v[1]) swap(v[0], v[1]);
            res += calc(v[0], f, (s + 1) / 2, n);
            if (s >= 2) res += calc(v[1], f, s / 2, n);
            v[0] += (s + 1) / 2 * f;
            v[1] += s / 2 * f;
        }
        rep(i, 2) assert(v[i] <= n / 2);
        res += (ll) n * (n + 1) / 2;
        return res;
    };
    vl ans(q);
    int nl = 0, nr = 0;
    for (int i: ord) {
//        cerr << i << endl;
        while (nl > l[i]) add(a[--nl]);
        while (nr < r[i]) add(a[nr++]);
        while (nl < l[i]) del(a[nl++]);
        while (nr > r[i]) del(a[--nr]);
        ans[i] = solve(r[i] - l[i]);
    }
    rep(i, q) cout << ans[i] << '\n';
}

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