Codeforces #1048 : Div1. B. Antiamuny Wants to Learn Swap

問題の不備でunratedになった回。
https://codeforces.com/contest/2138/problem/B

問題

整数列Aが与えられる。
クエリとしてAの部分列A[L...R]が指定されるので、以下を判定せよ。

A[L...R]に対し、以下を繰り返しソートすることを考える。

• 隣接する2要素をswapする
• 2つ隣にある2要素をswapする

後者を1回も使わない場合と、1回だけ使える場合で、ソートにかかる最小処理回数が一致するか判定せよ。

解法

後者を使うことで処理回数が減るのは、A'中にA'[i]＞A'[j]＞A'[k]となる3要素がある場合である。
nex(i) := A[i]＞A[j]となるi以上で最小のj
上記値をあらかじめ求めておく。

区間[L...R]中に、L≦x≦nex(nex(x))≦Rとなるxが存在すると、処理回数が減る。
区間最小値を求めるSegTreeにnex(nex(x))の値を乗せておけばこれを高速に判定できる。

int T;
int N,Q;
int A[505050],re[505050];
int L[505050],L2[505050];

template<class V,int NV> class SegTree_ma {
public:
	vector<V> val;
	static V const def=-1;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_ma(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_ma<int,1<<20> st;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>Q;
		FOR(i,N) {
			cin>>A[i];
			A[i]--;
			re[A[i]]=i;
			st.update(i,-1);
		}
		set<int> P={-1,N};
		
		for(i=N-1;i>=0;i--) {
			x=re[i];
			P.insert(x);
			auto it=P.find(x);
			L[x]=*prev(it);
			L2[x]=st.getval(0,x);
			st.update(x,L[x]);
		}
		
		
		FOR(i,N) {
			st.update(i,L2[i]);
		}
		
		while(Q--) {
			int LL,RR;
			cin>>LL>>RR;
			LL--;
			x=st.getval(LL,RR);
			if(x>=LL) {
				cout<<"NO"<<"\n";
			}
			else {
				cout<<"YES"<<"\n";
			}
		
		}
	}
	
		
	
}

まとめ

なんで通らないかわからない…と思ったら、とても重要な条件が後出しで出てきた。
こりゃunratedでもしょうがないよな…。