Submission #593234

#	Time	Username	Problem	Language	Result	Execution time	Memory
593234		SeDunion	Diversity (CEOI21_diversity)	C++17	100 / 100	4008 ms	8148 KiB

diversity

#include <iostream>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#ifndef LOCAL
	#include <bits/stdc++.h>
	#define cerr if(false)cerr
#endif
 
using namespace std;
using ll = long long;
 
const int N = 3e5 + 66;
 
ll a[N], n;
 
ll pref[N];

/*
summa(a[i]*(a[i]+1)/2 + a[i]*pref[i-1]*(i+1) - a[i]*(pref[n-1]-pref[i])*i)
summa((a[i]^2+a[i])/2 + a[i]*pref[i-1]*i+a[i]*pref[i-1] - a[i]*(pref[n-1]-pref[i])*i)
summa((a[i]^2+a[i])/2 + a[i]*pref[i]*i-a[i]^2*i + a[i]*pref[i-1] - a[i]*(pref[n-1]-pref[i])*i)
summa((a[i]^2+a[i])/2 + a[i]*pref[i]*i-a[i]^2*i + a[i]*pref[i]-a[i]^2 - a[i]*(pref[n-1]-pref[i])*i)
summa((a[i]^2+a[i])/2 + a[i]*pref[i]*i-a[i]^2*i + a[i]*pref[i]-a[i]^2 - a[i]*pref[n-1]*i - a[i]*pref[i]*i)
summa((a[i]^2+a[i])/2 + a[i]*pref[i]*i - a[i]^2*i + a[i]*pref[i]-a[i]^2 - a[i]*pref[n-1]*i - a[i]*pref[i]*i)
summa(a[i]/2 + a[i]*pref[i]*(i+1) - a[i]^2*i - a[i]^2/2 - a[i]*pref[n-1]*i - a[i]*pref[i]*i)
summa(a[i]/2 + a[i]*pref[i] - a[i]^2*i - a[i]^2/2 - a[i]*pref[n-1]*i)
summa(a[i]/2 + a[i]*pref[i] - a[i]^2*i - a[i]^2/2 - a[i]*pref[n-1]*i)
 */

ll f(ll s) { return s * (s + 1) / 2; }

//summa(f(pref[i - 1]) + f(pref[n - 1] - pref[i]))

ll solve() {
	ll ans = 0;
	for (int i = 0 ; i < n ; ++ i) {
		pref[i] = a[i];
		if (i) pref[i] += pref[i - 1];
	}
	for (int i = 0 ; i < n ; ++ i) {
		if (i) ans += f(pref[i - 1]);
		ans += f(pref[n - 1] - pref[i]);
	}
	ll C = n * f(pref[n-1]);
	// C = len * f(sum)
	return C-ans;
}

vector<int>vec;
int used[N];
int comp[N], freq[N];

void del(int v) {
	v = a[v];
	cerr << "del " << v << endl;
	comp[freq[v]]--;
	freq[v]--;
	if (freq[v] > 0 && !comp[freq[v]] && !used[freq[v]]) {
		used[freq[v]] = 1;
		vec.emplace_back(freq[v]);
	}
	comp[freq[v]]++;
}
void add(int v) {
	v = a[v];
	cerr << "add " << v << endl;
	comp[freq[v]]--;
	freq[v]++;
	if (freq[v] > 0 && !comp[freq[v]] && !used[freq[v]]) {
		used[freq[v]] = 1;
		vec.emplace_back(freq[v]);
	}
	comp[freq[v]]++;
}

using pll = pair<ll,ll>;
deque<pll>d;
int L, R;
ll sq(ll x) { return x*x; }
ll t(ll x) { return x*(x+1)*(2*x+1)/6; }
ll get() {
	for (int i = 0 ; i < (int)vec.size() ; ++ i) {
		if (!comp[vec[i]]) {
			used[vec[i]] = 0;
			swap(vec[i], vec.back());
			vec.pop_back();
			--i;
		}
	}
	sort(vec.rbegin(), vec.rend());
	ll q = 0;
	d.clear();
	int par = 0;
	int M = 0;
	for (int i : vec) { 
		M += comp[i];
		int lc, rc;
		if (par) lc = comp[i] / 2, rc = comp[i] - comp[i] / 2;
		else rc = comp[i] / 2, lc = comp[i] - comp[i] / 2;
		if (lc) d.push_front({i, lc});
		if (rc) d.push_back({i, rc});
		par ^= (comp[i] & 1);
	}
	int m = d.size(); ll pref = 0;
	cerr << "m ";
	for (int i = 0 ; i < m ; ++ i) cerr << "{" << d[i].first << ", " << d[i].second << "} ";
	cerr << endl;
	for (int i = 0 ; i < m ; ++ i) {
		q += d[i].second * sq(pref);
		q += 2 * pref * d[i].first * f(d[i].second - 1);
		q += sq(d[i].first) * t(d[i].second - 1); 
		pref += d[i].first * d[i].second;
		ll w = R-L+1-pref;
		q += d[i].second * sq(w);
		q += 2 * w * d[i].first * f(d[i].second - 1);
		q += sq(d[i].first) * t(d[i].second - 1); 
	}
	q = (ll)M * f(R-L+1) - ((ll)M * (R-L+1) - (R-L+1) + q) / 2;
	cerr << "get " << q << endl;
	return q;
}

ll ans[N];

int ql[N], qr[N];

vector<tuple<int,int,int>>MO;

const int K = 400;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int q;
	cin >> n >> q;
	for (int i = 0 ; i < n ; ++ i) cin >> a[i];
	for (int i = 0 ; i < q ; ++ i) {
		cin >> ql[i] >> qr[i];
		ql[i]--, qr[i]--;
		MO.emplace_back(ql[i]/K, qr[i], i);
	}
	sort(MO.begin(), MO.end());
	L = 1, R = 0;
	for (int $ = 0 ; $ < q ; ++ $) {
		int i = get<2>(MO[$]);
		int l = ql[i], r = qr[i];
		while (L > l) add(--L);
		while (R < r) add(++R);
		while (L < l) del(L++);
		while (R > r) del(R--);
		ans[i] = get();
	}
	for (int i = 0 ; i < q ; ++ i) {
		cout << ans[i] << "\n";
	}
	return 0;
	map<int,int>mp;
	for (int i = 0 ; i < n ; ++ i) mp[a[i]]++;
	vector<int>freq;
	for (auto [f, s] : mp) freq.emplace_back(s);
	sort(freq.rbegin(), freq.rend());
	deque<int>p;
	for (int i : freq) {
		if ((int)p.size() & 1) p.push_back(i);
		else p.push_front(i);
	}
	n = p.size();
	for (int i = 0 ; i < n ; ++ i) a[i] = p[i];
	cout << solve();
}

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