Codeforces #911 : Div2 F. Local Deletions

なるほど…。
https://codeforces.com/contest/1900/problem/F

問題

整数列xに対し、f(x)は以下を交互に繰り返し、xが1要素になるまでの操作回数とする。

• xからlocal minimumでない要素を取り除く
• xからlocal maximumでない要素を取り除く

整数列Aが与えられる。部分列A[L,R]が指定されるので、f(A[L,R])を答えよ。

解法

処理1回で半分以上の要素が消えるので、解は高々O(logN)である。

A全体に対し、f(A)を求める過程をあらかじめ求めておく。
Aの部分列に対しては、大体f(A)に対する処理と同じように変化するが、両端だけちょっと変化が異なる。
よって両端の差がある部分だけ覚えて処理して行こう。

int N,Q;
vector<int> L[20];
int P[202020];

vector<int> hoge(vector<int>& v,int step,int last) {
	vector<int> nex;
	int i;
	FOR(i,v.size()-last) {
		if(i&&step%2==0&&P[v[i]]>P[v[i-1]]) continue;
		if(i&&step%2==1&&P[v[i]]<P[v[i-1]]) continue;
		if(i+1<v.size()&&step%2==0&&P[v[i]]>P[v[i+1]]) continue;
		if(i+1<v.size()&&step%2==1&&P[v[i]]<P[v[i+1]]) continue;
		nex.push_back(v[i]);
	}
	return nex;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>P[i];
		L[0].push_back(i);
	}
	FOR(i,20) if(L[i].size()>1) L[i+1]=hoge(L[i],i,0);
	
	while(Q--) {
		int QL,QR;
		cin>>QL>>QR;
		if(QL>QR) swap(QL,QR);
		QL--;
		if(QL+1==QR) {
			cout<<P[QL]<<endl;
			continue;
		}
		vector<int> TL={QL},TR={QR-1};
		int CL=QL+1,CR=QR-2;
		int step=0;
		while(CL<=CR) {
			int CL2=lower_bound(ALL(L[step]),CL)-L[step].begin();
			int CR2=lower_bound(ALL(L[step]),CR)-L[step].begin();
			if(CR2-CL2<=10) break;
			vector<int> TL2,TR2;
			TL.push_back(CL);
			TL.push_back(L[step][CL2+1]);
			TR.push_back(CR);
			TR.push_back(L[step][CR2-1]);
			TL=hoge(TL,step,1);
			TR=hoge(TR,step,1);
			step++;
			x=lower_bound(ALL(L[step]),CL+1)-L[step].begin();
			y=lower_bound(ALL(L[step]),CR)-L[step].begin()-1;
			if(x>y) {
				CL=1,CR=0;
			}
			else {
				CL=L[step][x];
				CR=L[step][y];
			}
		}
		if(CL<=CR) {
			int CL2=lower_bound(ALL(L[step]),CL)-L[step].begin();
			int CR2=lower_bound(ALL(L[step]),CR)-L[step].begin();
			for(x=CL2;x<=CR2;x++) TL.push_back(L[step][x]);
		}
		reverse(ALL(TR));
		FORR(x,TR) TL.push_back(x);
		step%=2;
		
		while(TL.size()>1) {
			TL=hoge(TL,step,0);
			step^=1;
		}
		cout<<P[TL[0]]<<endl;
	}
	
}

まとめ

考え方は思いついても、細かいところ詰めるのが割と面倒。