Submission #1233872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233872		Matthewwww	Diversity (CEOI21_diversity)	C++17	64 / 100	7091 ms	69720 KiB

diversity

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif

const int sq = 821;

struct Sgt {
	ll l, r, v, t, e;
	int tl, tr;
	Sgt *lft, *rht;
	Sgt (int l, int r): l(0), r(0), v(0), t(0), e(1), tl(l), tr(r) {
		if (tl != tr-1) {
			int tm = tl+tr>>1;
			lft = new Sgt(tl, tm);
			rht = new Sgt(tm, tr);
		}
	}
	void update (int i, int x) {
		if (tl == tr-1) {
			ll d = t+x;
			l = r = t = d;
			v = d*(d+1)/2;
			return;
		}
		(i < lft->tr ? lft : rht)->update(i, x);
		l = lft->l+rht->l+lft->e*rht->t;
		r = lft->r+rht->r+lft->t*rht->e;
		v = lft->v+rht->v+lft->t*rht->l+lft->r*rht->t;
		t = lft->t+rht->t;
		e = lft->e+rht->e;
	}
};

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	vector<int> vt(n);
	for (int &i: vt) cin >> i;
	vector<int> cc(vt.begin(), vt.end());
	sort(cc.begin(), cc.end());
	cc.erase(unique(cc.begin(), cc.end()), cc.end());
	for (int &i: vt) i = lower_bound(cc.begin(), cc.end(), i)-cc.begin();
	int m = cc.size()+cc.size()%2;
	vector<int> cnt(m, 0);
	vector<int> tag(m);
	iota(tag.begin(), tag.end(), 0);
	Sgt *sgt[2];
	sgt[0] = new Sgt(0, m/2);
	sgt[1] = new Sgt(0, m/2);
	vector<map<int, int>> st(n+9);
	for (int i = 0; i < m; i++) st[0][tag[i]] = i;
	vector<pair<int, int>> qs(q);
	for (auto &i: qs) {
		cin >> i.f >> i.s;
		i.f--;
	}
	vector<vector<int>> bucket(n/sq+1);
	for (int i = 0; i < q; i++) bucket[qs[i].f/sq].push_back(i);
	for (auto &i: bucket) sort(i.begin(), i.end(), [&](int a, int b) { return qs[a].s < qs[b].s;});
	vector<int> ord;
	vector<ll> ans(q);
	for (auto i: bucket) for (int j: i) ord.push_back(j);
	int l = 0, r = 0;
	auto rmv = [&](int i) {
		if (st[cnt[i]].size()) {
			int h = (*st[cnt[i]].begin()).s;
			if (h != i) {
				st[cnt[i]].erase(tag[h]);
				st[cnt[i]][tag[i]] = h;
				swap(tag[h], tag[i]);
				cnt[i]--;
				st[cnt[i]][tag[i]] = i;
			} else {	
				st[cnt[i]].erase(tag[i]);
				cnt[i]--;
				st[cnt[i]][tag[i]] = i;
			}
		} else {	
			st[cnt[i]].erase(tag[i]);
			cnt[i]--;
			st[cnt[i]][tag[i]] = i;
		}
		sgt[tag[i]%2]->update(tag[i]/2, -1);
	};
	auto add = [&](int i) {
		if (st[cnt[i]].size()) {
			int h = (*--st[cnt[i]].end()).s;
			if (h != i) {
				st[cnt[i]].erase(tag[h]);
				st[cnt[i]][tag[i]] = h;
				swap(tag[h], tag[i]);
				cnt[i]++;
				st[cnt[i]][tag[i]] = i;
			} else {	
				st[cnt[i]].erase(tag[i]);
				cnt[i]++;
				st[cnt[i]][tag[i]] = i;
			}
		} else {	
			st[cnt[i]].erase(tag[i]);
			cnt[i]++;
			st[cnt[i]][tag[i]] = i;
		}
		sgt[tag[i]%2]->update(tag[i]/2, 1);
	};
	for (int i: ord) {
		auto p = qs[i];
		while (r < p.s) add(vt[r++]);
		while (l > p.f) add(vt[--l]);
		while (l < p.f) rmv(vt[l++]);
		while (r > p.s) rmv(vt[--r]);
		ans[i] = sgt[0]->v+sgt[1]->v+sgt[0]->t*sgt[1]->r+sgt[1]->t*sgt[0]->r;
	}
	for (ll i: ans) cout << i << "\n";
}

// no llama :(
// i miss you

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