Submission #697526

#	Time	Username	Problem	Language	Result	Execution time	Memory
697526		piOOE	Diversity (CEOI21_diversity)	C++17	64 / 100	7054 ms	72512 KiB

diversity

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct SegmentTree {
    vector<ll> t;
    vector<ll> tag;

    int sz;

    void init(vector<int> a) {
        int n = a.size();
        sz = 1 << __lg(n) + !!(n & (n - 1));
        t.resize(sz << 1), tag.resize(sz << 1);

        for (int i = 0; i < n; ++i) {
            t[i + sz] = a[i];
        }
        for (int i = sz - 1; i > 0; --i) {
            t[i] = t[i << 1] + t[i << 1 | 1];
        }
    }

    void rangeAdd(int l, int r, int v, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return;
        }

        if (l <= lx && rx <= r) {
            tag[x] += v;
            t[x] += 1LL * v * (rx - lx);
            return;
        }

        int mid = (lx + rx) / 2;

        rangeAdd(l, r, v, x << 1, lx, mid), rangeAdd(l, r, v, x << 1 | 1, mid, rx);

        t[x] = t[x << 1] + t[x << 1 | 1] + (rx - lx) * tag[x];
    }

    void rangeAdd(int l, int r, int v) {
        rangeAdd(l, r, v, 1, 0, sz);
    }

    ll rangeSum(int l, int r, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return 0;
        }

        if (l <= lx && rx <= r) {
            return t[x];
        }

        int mid = (lx + rx) / 2;

        return rangeSum(l, r, x << 1, lx, mid) + rangeSum(l, r, x << 1 | 1, mid, rx) +
               (min(rx, r) - max(lx, l)) * tag[x];
    }

    ll rangeSum(int l, int r) {
        return rangeSum(l, r, 1, 0, sz);
    }
} t[2][2]; // (left/right), (L/R)

struct Query {
    int l, r, block, idx;

    bool operator<(Query oth) const {
        if (oth.block != block) {
            return block < oth.block;
        }

        return (block & 1) ? r > oth.r : r < oth.r;
    }
};

constexpr int B = 500;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> a(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> yy = a;
    sort(yy.begin(), yy.end());
    yy.resize(unique(yy.begin(), yy.end()) - yy.begin());

    for (int &x: a) {
        x = lower_bound(yy.begin(), yy.end(), x) - yy.begin();
    }

    const int m = yy.size();

    vector<Query> queries(q);
    vector<ll> answer(q);

    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        l -= 1;

        queries[i].l = l, queries[i].r = r, queries[i].block = l / B, queries[i].idx = i;
    }

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

    vector<int> head(n + 1);

    for (int i = 1; i <= n; ++i) {
        head[i] = m;
    }

    t[0][0].init(vector(n, 0));
    t[0][1].init(vector(n, 0));
    t[1][0].init(vector(n, 0));
    t[1][1].init(vector(n, 0));

    vector<int> pos(m), cnt(m), ord(m);
    iota(pos.begin(), pos.end(), 0);
    ord = pos;

    int siz[2]{(m + 1) / 2, m / 2};

    ll ans = 0;

    int len = 0;

    auto eval = [&](int i) {
        return 1LL * cnt[i] * (len - cnt[i]) + 1LL * (cnt[i] + 1) * cnt[i] / 2;
    };

    auto increase = [&](int i) {
        ans += len;

        len += 1;

        ans -= eval(i);

        int p = pos[i];
        int tail = head[cnt[i] + 1] - 1;

        if (p != tail) {
            int id = ord[tail];
            pos[id] = p;
            ord[p] = id;
            pos[i] = tail;
            ord[tail] = i;
            p = tail;
        }

        int side = p % 2;
        int s = p / 2;

        if (side) {
            ans += t[side][0].rangeSum(s + 1, siz[side]);
            t[side][1].rangeAdd(s + 1, siz[side], 1);

            t[side][0].rangeAdd(0, s, 1);
            ans += t[side][1].rangeSum(0, s);

            ans += t[side ^ 1][0].rangeSum(0, siz[side ^ 1]);
            t[side ^ 1][1].rangeAdd(0, siz[side ^ 1], 1);
        } else {
            ans += t[side][1].rangeSum(s + 1, siz[side]);
            t[side][0].rangeAdd(s + 1, siz[side], 1);

            t[side][1].rangeAdd(0, s, 1);
            ans += t[side][0].rangeSum(0, s);

            ans += t[side ^ 1][1].rangeSum(0, siz[side ^ 1]);
            t[side ^ 1][0].rangeAdd(0, siz[side ^ 1], 1);
        }

        cnt[i] += 1;
        head[cnt[i]] = p;

        ans += eval(i);
    };

    auto decrease = [&](int i) {
        ans -= len;

        len -= 1;

        ans -= eval(i);

        int p = pos[i];
        int start = head[cnt[i]];

        if (p != start) {
            int id = ord[start];
            pos[id] = p;
            ord[p] = id;
            pos[i] = start;
            ord[start] = i;
            p = start;
        }

        int side = p % 2;
        int s = p / 2;

        if (side) {
            ans -= t[side][0].rangeSum(s + 1, siz[side]);
            t[side][1].rangeAdd(s + 1, siz[side], -1);

            t[side][0].rangeAdd(0, s, -1);
            ans -= t[side][1].rangeSum(0, s);

            ans -= t[side ^ 1][0].rangeSum(0, siz[side ^ 1]);
            t[side ^ 1][1].rangeAdd(0, siz[side ^ 1], -1);
        } else {
            ans -= t[side][1].rangeSum(s + 1, siz[side]);
            t[side][0].rangeAdd(s + 1, siz[side], -1);

            t[side][1].rangeAdd(0, s, -1);
            ans -= t[side][0].rangeSum(0, s);

            ans -= t[side ^ 1][1].rangeSum(0, siz[side ^ 1]);
            t[side ^ 1][0].rangeAdd(0, siz[side ^ 1], -1);
        }

        head[cnt[i]] = p + 1;
        cnt[i] -= 1;

        ans += eval(i);
    };

    int lx = 0, rx = 0;

    for (auto [l, r, bl, i] : queries) {
        while (rx < r) {
            increase(a[rx++]);
        }

        while (lx > l) {
            increase(a[--lx]);
        }

        while (lx < l) {
            decrease(a[lx++]);
        }

        while (rx > r){
            decrease(a[--rx]);
        }

        answer[i] = ans;
    }

    for (int i = 0; i < q; ++i) {
        cout << answer[i] << '\n';
    }

    return 0;
}

Compilation message (stderr)

diversity.cpp: In member function 'void SegmentTree::init(std::vector<int>)':
diversity.cpp:14:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   14 |         sz = 1 << __lg(n) + !!(n & (n - 1));
      |                   ~~~~~~~~^~~~~~~~~~~~~~~~~

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