Submission #790577

#	Time	Username	Problem	Language	Result	Execution time	Memory
790577		CSQ31	Diversity (CEOI21_diversity)	C++17	100 / 100	3684 ms	6340 KiB

diversity

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
//typedef long long int ll;
typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
const int MAXN = 3e5+5,blk = 547;
int a[MAXN],cnt[MAXN],freq[MAXN],smol[MAXN];
vector<int>large;
struct que{
	int l,r,id;
	que(){}
	que(int _l,int _r,int _id):l(_l),r(_r),id(_id){}
	bool operator<(const que &q){
		if((l+blk-1)/blk &1)return make_pair((l+blk-1)/blk,r) < make_pair((q.l+blk-1)/blk,q.r);
		return make_pair((l+blk-1)/blk,-r) < make_pair((q.l+blk-1)/blk,-q.r);
	}
};
void add(int x,int c){
	if(smol[x])freq[cnt[x]]--;
	cnt[x]+=c;
	if(smol[x])freq[cnt[x]]++;
}
vector<ll> get(){
	vector<ll>v,u;
	for(int x:large){
		if(!cnt[x])continue;
		freq[cnt[x]]++;
		if(cnt[x]>blk)u.pb(cnt[x]);
	}
	for(int i=1;i<=blk;i++){
		if(freq[i])v.pb(i);	
	}
	sort(all(u));
	for(int i=0;i<sz(u);i++){
		int j = i;
		while(j+1<sz(u) && u[j] == u[j+1])j++;
		i = j;
		v.pb(u[i]);
	}
	return v;
}
ll cal(ll n){
	vector<ll>v = get();
	int t = sz(v);
	ll T = 0;
	for(auto x:v)T+=freq[x];
	vector<int>in(t,0);
	//ans = 1/2(T*n*n + n - sum of squares)
	//for(int x:v)cout<<x<<" ";cout<<'\n';
	//for(int x:v)cout<<freq[x]<<" ";cout<<'\n';
	ll res = 0,cur = 0;
	for(int i=1;i<t;i++){
		in[i] = in[i-1]+(freq[v[i]]&1);
		in[i]%=2;
	}
	//S = (cur+v)^2 + (cur+2v)^2 + ... + (cur+xv)^2
	//  = x*cur*cur - 2cur*v(1+2+...+x) + v^2(1^2+2^2+3^2...x2);
	
	//(n-cur-v)^2 + (n-cur-2v)^2 + ... + (n-cur-xv)^2;
	//= x*n*n - 2*n( x*cur + v+2v+3v..+xv) + S
	vector<ll>tmp;
	for(int i=0;i<t;i++){
		ll x = (freq[v[i]]+in[i])/2;
		
		ll y = x*(x+1)/2;
		ll z = (x*(x+1)*(2*x+1))/6;
		
		ll S = 0;
		S+=x*cur*cur;
		S+=2*cur*v[i]*y;
		S+=v[i]*v[i]*z;
		res-=x*n*n;
		res+=2*n*( x*cur + y*v[i]);
		res-=2*S;
		cur+=x*v[i];
		for(int j=0;j<x;j++)tmp.pb(v[i]);
	}
	for(int i=t-1;i>=0;i--){
		ll x = (freq[v[i]]+in[i])/2;
		x = freq[v[i]]-x;
		ll y = x*(x+1)/2;
		ll z = (x*(x+1)*(2*x+1))/6;
		
		ll S = 0;
		S+=x*cur*cur;
		S+=2*cur*v[i]*y;
		S+=v[i]*v[i]*z;
		assert(S>=0);
		res-=x*n*n;
		res+=2*n*( x*cur + y*v[i]);
		res-=2*S;
		cur+=x*v[i];
	}
	res+=T*n*n+n;
	res+=n*n;
	for(int x:large){
		if(cnt[x])freq[cnt[x]]--;
	}
	return res/2;
}
int main()
{
	owo
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		cnt[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		if(!cnt[i])continue;
		if(cnt[i]<=blk)smol[i] = 1;
		else large.pb(i);
		cnt[i] = 0;
	}
	vector<que>qq(q);
	for(int i=0;i<q;i++){
		int l,r;
		cin>>l>>r;
		qq[i] = que(l,r,i);
	}
	sort(all(qq));
	vector<ll>ans(q);
	int L = 1,R = 0;
	for(int i=0;i<q;i++){
		int l = qq[i].l;
		int r = qq[i].r;
		while(L>l){
			L--;
			add(a[L],1);
		}
		while(R<r){
			R++;
			add(a[R],1);
		}
		while(L<l){
			add(a[L],-1);
			L++;
		}
		while(R>r){
			add(a[R],-1);
			R--;
		}
		ans[qq[i].id] = cal(r-l+1);	
	}
	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