Submission #576034

#	Time	Username	Problem	Language	Result	Execution time	Memory
576034		8e7	Diversity (CEOI21_diversity)	C++17	100 / 100	966 ms	10564 KiB

diversity

//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 300005
#define mod 998244353
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int bs = 1100;
struct query{
	int l, r, id;
	query(){l = r = id = 0;}	
	query(int a, int b, int c){l = a, r = b, id = c;}
};
int a[maxn], c[maxn], occ[maxn];
int lef[maxn], rig[maxn];
ll ans[maxn];

int distinct = 0;
void add(int col) {
	int &p = c[col];
	if (p == 0) distinct++;
	if (occ[p] == 1) {
		if (occ[p+1]) {
			rig[lef[p]] = rig[p];
			lef[rig[p]] = lef[p];
		} else {
			rig[lef[p]] = p+1;
			lef[rig[p]] = p+1;
			rig[p+1] = rig[p];
			lef[p+1] = lef[p];
		}
		lef[p] = 0, rig[p] = maxn-1;	
	} else if (occ[p+1]==0) {
		rig[p+1] = rig[p];
		lef[p+1] = p;

		lef[rig[p]] = p+1;
		rig[p] = p+1;
	}
	occ[p]--, occ[p+1]++;
	p++;
}
void del(int col) {
	int &p = c[col];
	if (p == 1) distinct--;
	if (occ[p] == 1) {
		if (occ[p-1]) {
			rig[lef[p]] = rig[p];
			lef[rig[p]] = lef[p];
		} else {
			rig[lef[p]] = p-1;
			lef[rig[p]] = p-1;
			rig[p-1] = rig[p];
			lef[p-1] = lef[p];
		}
		lef[p] = 0, rig[p] = maxn-1;	
	} else if (occ[p-1]==0) {
		rig[p-1] = p;
		lef[p-1] = lef[p];

		rig[lef[p]] = p-1;
		lef[p] = p-1;
	}

	occ[p]--, occ[p-1]++;
	p--;
}
int tot;

ll quad[maxn], cube[maxn];
ll getval(ll A, ll P, ll K) { //sum of A^2 + (A+P)^2 + ... + (A+(K-1)P)^2 + A + (A+P) + ... + (A + (K-1)P)
	return K * (A * (A+1) + (tot - K*P-A)*(tot-K*P-A+1)) + quad[K] * (2*(tot-K*P+1)) * P + 2*cube[K] * P * P;
}
ll getans() {
	int cur = rig[0];
	ll ret = 0;
	ll lc = 0, rc = 0;
	while (cur <= tot) {
		if (lc > rc) swap(lc, rc);
		ll p = cur;
		//debug(cur, occ[p]);
		ll pl = (occ[p] + 1)/2, pr = occ[p] / 2;
		ret += getval(lc, p, pl) + getval(rc, p, pr);

		lc += pl * p, rc += pr * p;
		cur = rig[cur];
	}
	return ret / 2;
}
int main() {
	io
	for (ll i = 1;i < maxn;i++) {
		quad[i] = i * (i-1) / 2;	
		cube[i] = (i-1) * i * (2 * i - 1) / 6;
	}

	ll n, q;
	cin >> n >> q;
	for (int i = 0;i < n;i++) {
		cin >> a[i];
	}
	for (int i = 0;i <= n;i++) rig[i] = maxn-1;
	occ[0] = maxn-1;
	vector<query> que;
	for (int i = 0;i < q;i++) {
		int l, r;
		cin >> l >> r;
		l--, r--;
		que.push_back(query(l, r, i));
	}
	sort(que.begin(), que.end(), [&](query x, query y){
		return x.l / bs == y.l / bs ? ((x.l / bs & 1) ? x.r < y.r : x.r > y.r) : (x.l < y.l);});
	int cl = 0, cr = -1;
	for (auto [l, r, id]:que) {
		while (cr < r) add(a[++cr]);
		while (cl > l) add(a[--cl]);
		while (cr > r) del(a[cr--]);
		while (cl < l) del(a[cl++]);
		ans[id] = quad[r - l + 2] * distinct;
		tot = r - l + 1;
		ans[id] -= getans();
	}
	for (int i = 0;i < q;i++) 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