Codeforces #586 F. Gardener Alex

本番通しきれなかったのは残念。
https://codeforces.com/contest/1220/problem/F

問題

1～NのPermutationを成す数列が与えられる。
この数列に対し、左右の相対的な位置を維持したまま二分木を構築することを考える。
このPermutationを任意回数Rotateできるとき、木の高さを最小化せよ。

解法

1が右端にある状態から初めて、左に1個ずつRotateしたとする。
この時、木の変化量はさほど大きくない、というか均しで1回O(1)である。
よって区間加算・区間最大値をとれるSegTreeがあれば1の右側の木の高さの最大値を随時追うことができる。

同様に、1が左側にある状態から初めて、右にRotateしたときの木の左側の高さも求めていこう。
最終的に、各Rotate回数に対応する左と右の木の高さを求めることができる。

template<class V,int NV> class RMQ_range {
public:
	vector<V> val, ma;
	RMQ_range(){ val.resize(NV*2,0); ma.resize(NV*2,0); };
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return 0;
		if(x<=l && r<=y) return ma[k];
		return max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1)) + val[k];
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=max(ma[k*2],ma[k*2+1]) + val[k];
		}
	}
};
RMQ_range<int,1<<20> rmq;

int N;
int A[606060];
int R[606060];
int L[606060];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int C;
	FOR(i,N) {
		cin>>A[i];
		A[i+N]=A[i];
		A[i+2*N]=A[i];
		if(A[i]==1) C=i+N;
	}
	
	rmq.update(C,C+1,1);
	vector<pair<int,int>> V;
	V.push_back({C,1});
	L[0]=R[0]=1;
	for(r=1;r<N;r++) {
		while(A[V.back().first]>A[C+r]) V.pop_back();
		x=V.back().first+1;
		y=V.back().second+1;
		rmq.update(x,C+r,1);
		rmq.update(C+r,C+r+1,y);
		V.push_back({C+r,y});
		R[r]=rmq.getval(C,C+r+1);
	}
	V.clear();
	V.push_back({C,1});
	for(r=1;r<N;r++) {
		while(A[V.back().first]>A[C-r]) V.pop_back();
		x=V.back().first;
		y=V.back().second+1;
		rmq.update(C-r+1,x,1);
		rmq.update(C-r,C-r+1,y);
		V.push_back({C-r,y});
		L[r]=rmq.getval(C-r,C+1);
	}
	int mi=1<<20;
	int rot=0;
	int curL=C-N;
	FOR(i,N) {
		x=max(L[curL],R[N-1-curL]);
		if(x<mi) mi=x, rot=i;
		curL--;
		if(curL<0) curL=N-1;
	}
	cout<<mi<<" "<<rot<<endl;
	
	
}

まとめ

言われてみると簡単なんだけどね。