Submission #814790

#	Time	Username	Problem	Language	Result	Execution time	Memory
814790		khshg	Diversity (CEOI21_diversity)	C++14	100 / 100	6842 ms	10744 KiB

diversity

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array

const int maxn = 300000, maxq = 50000, B = 3333;
int N, Q;
int A[maxn], cnt[maxn], l[maxn + 1], r[maxn + 1];
ar<int, 3> q[maxn];
ll cur, ans[maxq];
ar<ll, maxn + 1> pref, LtoR, RtoL;

void add(ar<ll, maxn + 1>& a, int i, ll val) {
	++i;
	while(i <= maxn) {
		a[i] += val;
		i += i & -i;
	}
}

ll sum(ar<ll, maxn + 1>& a, int p) {
	ll ans = 0;
	while(p) {
		ans += a[p];
		p -= p & -p;
	}
	return ans;
}

ll sum(ar<ll, maxn + 1>& a, int l, int r) {
	return sum(a, r + 1) - sum(a, l);
}

int prv(int x) {
	if(x <= (N - 1) / 2) return N - x;
	else return N - x - 1;
}
 
int nxt(int x) {
	if(x <= N / 2) return N - x - 1;
	else return N - x;
}


void add(int i) {
	int v = A[i];
	i = r[cnt[v]];
	assert(i >= 0 && i < N);
	if(l[cnt[v]] == r[cnt[v]]) {
		l[cnt[v]] = r[cnt[v]] = -1;
	} else {
		r[cnt[v]] = prv(i);
	}
	cur += ++cnt[v];
	if(i + 1 <= N - 1) cur += sum(LtoR, i + 1, N - 1) - sum(pref, i + 1, N - 1) * i;
	if(0 <= i - 1) cur += sum(RtoL, 0, i - 1) - sum(pref, 0, i - 1) * (N - 1 - i);
	add(LtoR, i, i + 1);
	add(RtoL, i, N - i);
	add(pref, i, 1);
	if(l[cnt[v]] == -1) l[cnt[v]] = r[cnt[v]] = i;
	else l[cnt[v]] = i;
}

void rem(int i) {
	int v = A[i];
	i = l[cnt[v]];
	if(l[cnt[v]] == r[cnt[v]]) {
		l[cnt[v]] = r[cnt[v]] = -1;
	} else {
		l[cnt[v]] = nxt(i);
	}
	cur -= cnt[v]--;
	if(i + 1 <= N - 1) cur -= sum(LtoR, i + 1, N - 1) - sum(pref, i + 1, N - 1) * i;
	if(0 <= i - 1) cur -= sum(RtoL, 0, i - 1) - sum(pref, 0, i - 1) * (N - 1 - i);
	add(LtoR, i, -(i + 1));
	add(RtoL, i, -(N - i));
	add(pref, i, -1);
	if(l[cnt[v]] == -1) l[cnt[v]] = r[cnt[v]] = i;
	else r[cnt[v]] = i;
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> N >> Q;
	l[0] = 0;
	r[0] = N / 2;
	for(int i = 0; i < N; ++i) {
		l[i + 1] = r[i + 1] = -1;
		cin >> A[i];
		--A[i];
	}
	for(int i = 0; i < Q; ++i) {
		for(int x : {0, 1}) { cin >> q[i][x]; --q[i][x]; }
		q[i][2] = i;
	}
	sort(q, q + Q, [&](const ar<int, 3>& a, const ar<int, 3>& b) {
		if(a[0] / B == b[0] / B) return (bool)((a[1] < b[1]) ^ ((a[0] / B) & 1));
		return ((a[0] / B) < (b[0] / B));
	});
	for(int i = 0, L = 0, R = 0; i < Q; ++i) {
		int ql = q[i][0], qr = q[i][1];
		while(R <= qr) add(R++);
		while(L < ql) rem(L++);
		while(L > ql) add(--L);
		while(R > qr + 1) rem(--R); // erkhes sussy
		ans[q[i][2]] = cur;
	}
	for(int i = 0; i < Q; ++i) {
		cout << ans[i] << '\n';
	}
	return 0;
}

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