Submission #476950

#	Time	Username	Problem	Language	Result	Execution time	Memory
476950		MetalPower	Diversity (CEOI21_diversity)	C++14	100 / 100	2626 ms	7988 KiB

diversity

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second

const int MX = 3e5 + 10;
const int SQ = 605;

struct queries{
	int l, r, id;

	bool operator < (queries& b) const{
		int _a = l / SQ, _b = b.l / SQ;
		return (_a < _b) || (_a == _b && r < b.r);
	}
};

vector<queries> q;

int N, Q, arr[MX];
int cnt[MX]; // number of values with freq i
int freq[MX];

ll ans[MX];

void upd(int p, int v){
	if(freq[p] < SQ) cnt[freq[p]]--;
	freq[p] += v;
	if(freq[p] < SQ) cnt[freq[p]]++;
}

vector<int> lg;
vector<pii> val;

void init(){

	val.clear();

	for(int j = 1; j < SQ; j++)
		val.push_back({j, cnt[j]});

	vector<int> temp;

	for(auto j : lg){
		if(freq[j] >= SQ){
			cnt[freq[j]]++;
			temp.push_back(freq[j]);
		}
	}

	sort(temp.begin(), temp.end());
	temp.resize(unique(temp.begin(), temp.end()) - temp.begin());

	for(auto j : temp){
		val.push_back({j, cnt[j]});
		cnt[j] = 0;
	}
}

ll sum(ll a, ll r, ll n){ // a^2 + (a + r)^2 + (a + 2r)^2 + ... (a + nr)^2
	return a * a * (n + 1) + a * r * n * (n + 1) + r * r * (n * (n + 1) * (n + n + 1) / 6);
}

ll solve(){

	int st = 1, _N = 0, _K = 0;
	int suml = 0, sumr = 0; 

	ll curr = 0;

	for(auto p : val){
		_N += p.fi * p.se;
		_K += p.se;
	}

	for(auto p : val){

		int l = (p.se + st) >> 1;
		int r = (p.se + 1 - st) >> 1;

		curr += sum(suml, p.fi, l - 1);
		curr += sum(_N - suml - p.fi, -p.fi, l - 1);

		curr += sum(sumr, p.fi, r - 1);
		curr += sum(_N - sumr - p.fi, -p.fi, r - 1);

		suml += p.fi * l;
		sumr += p.fi * r;

		st ^= p.se & 1;
	}

	return ((ll) _K * _N * (_N + 1) - (ll) _N * (_K - 1) - curr) >> 1;
}

void answer(){

	int l = 0, r = -1;

	for(auto p : q){
		while(r < p.r) upd(arr[++r], 1);
		while(r > p.r) upd(arr[r--], -1);
		while(l < p.l) upd(arr[l++], -1);
		while(l > p.l) upd(arr[--l], 1);
		init();
		ans[p.id] = solve();
	}
}

int tfreq[MX];

int main(){
	scanf("%d %d", &N, &Q);

	vector<int> cd;

	for(int i = 0; i < N; i++){
		cin >> arr[i];
		cd.push_back(arr[i]);
	}

	sort(cd.begin(), cd.end());
	cd.resize(unique(cd.begin(), cd.end()) - cd.begin());

	for(int i = 0; i < N; i++){
		arr[i] = lower_bound(cd.begin(), cd.end(), arr[i]) - cd.begin();
		tfreq[arr[i]]++;
	}

	for(int i = 0; i < N; i++){
		if(tfreq[i] >= SQ) 
			lg.push_back(i);
	}

	for(int i = 0; i < Q; i++){
		int l, r; cin >> l >> r;
		l--; r--;
		q.push_back({l, r, i});
	}

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

	answer();

	for(int i = 0; i < Q; i++)
		cout << ans[i] << '\n';
}

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |  scanf("%d %d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~

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