제출 #1189560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1189560		Faisal_Saqib	Diversity (CEOI21_diversity)	C++20	64 / 100	7095 ms	6552 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10,SQ=1342;// 1342
const int M=N/SQ+10;
#define ll long long 
#define vl vector<ll>
#define all(x) x.begin(),x.end() 
#define rall(x) x.rbegin(),x.rend() 
#define pb push_back
vl get_order(vl inp)
{
	vl bas=inp,b,bag,bbk;
	sort(all(bas));
	for(int i=0;i<bas.size();i++)
	{
		if(i%2==0)
		{
			bag.pb(bas[i]);
		}
		else
		{
			bbk.pb(bas[i]);
		}
	}
	reverse(all(bbk));
	b=bag;
	for(auto x:bbk)
	{
		b.pb(x);
	}
	return b;
}
int a[N],cnt[N],ccnt[N];
ll ans[N];
vector<vector<int>> query[M];
set<int> dif; // try to change to unordered
void add(int idx)
{
	// cout<<endl;
	// cout<<"Adding "<<a[idx]<<endl;
	// cout<<endl;
	if(cnt[a[idx]]!=0)
	{
		--ccnt[cnt[a[idx]]];
		if(ccnt[cnt[a[idx]]]==0)
			dif.erase(cnt[a[idx]]);
	}
	++cnt[a[idx]];
	if(ccnt[cnt[a[idx]]]==0)
			dif.insert(cnt[a[idx]]);
	++ccnt[cnt[a[idx]]];
}
void rem(int idx)
{
	// cout<<endl;
	// cout<<"Removing "<<a[idx]<<endl;
	// cout<<endl;
	--ccnt[cnt[a[idx]]];
	if(ccnt[cnt[a[idx]]]==0)
		dif.erase(cnt[a[idx]]);
	--cnt[a[idx]];
	if(cnt[a[idx]] != 0)
	{
		if(ccnt[cnt[a[idx]]]==0)
			dif.insert(cnt[a[idx]]);
		++ccnt[cnt[a[idx]]];
	}
}
ll f(ll x)
{
	return (x*(x+1))/2;
}
ll g(ll x)
{
	// f(1)+f(2)+f(3)+..+f(x)
	// 2C2 + 3C2 +4C2+ .. + (x+1)C2 == x+2 C 3
	return ((x+2)*(x+1)*x)/6;
}
void solve()
{
	int n,q;
	cin>>n>>q;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	// sort(a,a+n);
	for(int id=0;id<q;id++)
	{
		int l,r;
		cin>>l>>r;
		ll len=(r-l+1);
		ans[id]=(len*(len+1))/2;
		l--;
		int bl=l/SQ;
		query[bl].push_back({r,id,l});
	}
	int cl=0,cr=0;
	// [cl,cr)
	// inclusive exclusive
	for(int cb=0;cb<=(n/SQ);cb++)
	{
		// cl<=cr
		cr=cl=0;
		sort(all(query[cb]));
		for(auto qry:query[cb])
		{
			int r=qry[0],id=qry[1],l=qry[2];
			while(cl<l)
			{
				rem(cl);
				cl++;
			}
			while(l<cl)
			{
				cl--;
				add(cl);
			}
			while(cr<r)
			{
				// cout<<"Do "<<cr<<' '<<a[cr]<<endl;
				add(cr);
				cr++;
			}
			int tl=0;
			// cout<<"Range "<<cl<<' '<<cr<<endl;
			// cout<<l<<' '<<r<<endl;
			vector<pair<ll,ll>> part[2]={};// array is compressed 
			// RLE
			// (x,c) x appear c times
			// cout<<"Query "<<l<<' '<<r<<" index "<<id<<endl;
			for(auto x:dif) // O(sqrt(N))
			{
				// cout<<"Cnt of cnt = "<<x<<" is "<<ccnt[x]<<endl;
				part[tl%2].pb({x,(ccnt[x]+1)/2});
				part[1-tl%2].pb({x,ccnt[x]/2});
				tl=(tl+ccnt[x])%2;
			}
			// reverse(all(part[1]));// O(sqrt(N))
			for(int j=part[1].size();j>=1;j--)
			{
				part[0].pb(part[1][j-1]);
			}
			ll len=r-l;
			ll sm=0;
			ll cu=0;
			// f(x) = x*(x+1)/2
			// cout<<"Order: ";
			for(auto xp:part[0])
			{
				// cout<<xp.first<<' '<<xp.second<<endl;
				//  Val cu          Val to add sm
				// cu+1*xp.first      len-cu-1*xp.first
				// cu+2*xp.first      2*len-2*cu-(1+2)*xp.first
				// cu+3*xp.first      3*len-3*cu-(1+2+3)*xp.first
				//    .                       .
				//    .                       .
				//    .                       .
				// xp.second*xp.first      xp.second*len-xp.second*cu-f(xp.second)*xp.first
				sm+=(xp.second*len-xp.second*cu-f(xp.second)*xp.first);
				cu+=(xp.second*xp.first);
			}
			cu=0;
			for(auto xp:part[0])
			{
				// xp = (x,y)
				//ans[id] + 1*x*sm			                 cu+x      sm-len+cu+x     
				//ans[id] + 2*x*sm - x*len + x*cu + x*x      cu+2*x     sm-2*len+2*cu+f(2)*x
				//ans[id] + 3*x*sm - f(2)*x*len + f(2)*x*cu + (f(1)+f(2))*x*x      cu+2*x     sm-3*len+3*cu+f(3)*x
				// .
				// .
				// .
				// .
				// ans[id]= y*x*sm - f(y-1)*x*len + f(y-1)*x*cu + (f(1)+f(2)+..+f(y-1))*x*x
				ll x=xp.first;
				ll y=xp.second;
				ans[id]+=y*x*sm - f(y-1)*x*len + f(y-1)*x*cu + (g(y-1))*x*x;
				sm-=y*len;
				sm+=(y*cu);
				sm+=(f(y)*x);
				cu+=(x*y);
			}
			// for(auto x:b)
			// {
			// 	fnl+=(x*sm);
			// 	cu+=x;
			// 	sm-=(len-cu);
			// }
			// return fnl;
		}
		while(cl<cr)
		{
			rem(cl);
			cl++;
		}
		// cout<<"Left with "<<cl<<' '<<cr<<' '<<dif.size()<<endl;
	}
	for(int i=0;i<q;i++)
	{
		cout<<ans[i]<<'\n';
	}
	// cout<<endl;
	// ll fnl=0;
	// // for(int i=0;i<n;i++)
	// // {
	// // 	set<int> cur;
	// // 	for(int j=i;j<n;j++)
	// // 	{
	// // 		cur.insert(a[j]);
	// // 		fnl+=(ll)cur.size();
	// // 	}
	// // }
	// vl xp;
	// for(int i=1;i<N;i++)
	// {
	// 	if(cnt[i])
	// 	{
	// 		xp.pb(cnt[i]);
	// 	}
	// }
	// // sort(all(xp));
	// xp=get_order(xp);
	// int m=xp.size();
	// vl pre(m+2),suf(m+2);
	// ll cp=0;
	// for(int i=1;i<=m;i++)
	// {
	// 	pre[i]=pre[i-1]+xp[i-1];
	// 	cp+=(n-pre[i]);
	// }
	// for(int i=0;i<m;i++)
	// {
	// 	fnl+=(xp[i]*cp);
	// 	cp-=(n-pre[i+1]);
	// }
	// fnl+=((n*(n+1))/2);
	// cout<<fnl<<endl;
}
int32_t main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	// cin>>t;
	while(t--)solve();	
	return 0;
}

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