Codeforces ECR #103 : G. Minimum Difference

これああんまり記憶がないなぁ。
https://codeforces.com/contest/1476/problem/G

問題

N要素の整数列Aに対し、以下のクエリに順次答えよ。

• 1要素を指定された値に上書きする。
• 区間[L,R]と正整数Kが与えられる。A[L...R]のうち、K通りの値(ただし、各値はA[L..R]中に1回以上登場しなければならない)を選ぶ。
  • その時、選んだ値の登場頻度の最大値と最小値の差の最小値を答えよ。

解法

時間と添え字の二軸でMo's Algorithmを使っていくとよい。

K通りの値の数え方だが、頻度を小さい順に格納した数列を管理しよう。
頻度の組み合わせは√N通りなので、小さい方の頻度を総当たりしても間に合う。

int N,M;
int A[201010];
vector<vector<int>> event;
vector<vector<int>> update;
int ret[201010];
const int DI=2222;

int C[201010];
int ord[201010];
int L[201010],R[201010];

void inc(int v) {
	int pos=L[C[v]]++;
	ord[pos]++;
	C[v]++;
	if(L[C[v]]==R[C[v]]) {
		L[C[v]]=pos;
		R[C[v]]=pos+1;
	}
	else {
		R[C[v]]=pos+1;
	}
}

void del(int v) {
	int pos=--R[C[v]];
	ord[pos]--;
	C[v]--;
	if(L[C[v]]==R[C[v]]) {
		L[C[v]]=pos;
		R[C[v]]=pos+1;
	}
	else {
		L[C[v]]=pos;
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	FOR(i,M) {
		cin>>j;
		if(j==1) {
			cin>>l>>r>>x;
			l--,r--;
			int tim=101010*(update.size()/DI*100 + l/DI);
			if(l/DI%2==0) tim+=r;
			else tim+=100010-r;
			event.push_back({tim,l,r,x,(int)update.size(),(int)event.size()});
		}
		else {
			cin>>x>>y;
			x--;
			update.push_back({x,A[x],y});
			A[x]=y;
		}
	}
	//巻き戻し
	for(i=update.size()-1;i>=0;i--) A[update[i][0]]=update[i][1];
	L[0]=0;
	R[0]=N;
	sort(ALL(event));
	int CL=0,CR=-1,CT=0;
	FORR(e,event) {
		int TL=e[1];
		int TR=e[2];
		int K=e[3];
		int TT=e[4];
		int& r=ret[e[5]];
		r=1<<20;
		while(CT<TT) {
			x=update[CT][0];
			if(x>=CL&&x<=CR) del(A[x]);
			A[x]=update[CT][2];
			if(x>=CL&&x<=CR) inc(A[x]);
			CT++;
		}
		while(CT>TT) {
			CT--;
			x=update[CT][0];
			if(x>=CL&&x<=CR) del(A[x]);
			A[x]=update[CT][1];
			if(x>=CL&&x<=CR) inc(A[x]);
		}
		while(TL<CL) inc(A[--CL]);
		while(CR<TR) inc(A[++CR]);
		while(CL<TL) del(A[CL++]);
		while(TR<CR) del(A[CR--]);
		
		int cur=0;
		while(ord[cur]) {
			if(ord[cur+(K-1)]) r=min(r,ord[cur]-ord[cur+(K-1)]);
			cur=R[ord[cur]];
		}
		if(r==1<<20) r=-1;
	}
	FOR(i,event.size()) cout<<ret[i]<<endl;
}

まとめ

二軸のMo、覚えておこう…。