kmjp's blog

競技プログラミング参加記です

Codeforces ECR #067 : D. Subarray Sorting

ECRでラスト2問が難しいのは珍しいよね。
https://codeforces.com/contest/1187/problem/D

問題

整数列A,Bが与えられる。
Aの部分列を選択し、そこだけ昇順にソートする、ということを繰り返しAをBにできるか。

解法

まずBの各要素がAの何番目からくるかを求めよう。

もしB[i]=cとなる要素がBにおいて先頭からd個目の場合、Aのd個目にある要素がB[i]に来る。
これは容易に求められる。

あとは、この関係で矛盾を生じるケースがあるかをチェックする。
例えばB[i]はA[a]、B[j]はA[b]の要素を持ってくるようにしたいとする。
この時、B[i]>B[j]かつi<j<b<aだとよろしくない。
なぜならB[i]にA[a]を持って来ようと、A[i...a]をソートしてしまうと、その最小値はA[a]より小さくなってしまうためである。

これは最大値を求めるSegTreeを作り、Bにおいて自身より手前にある自分より小さい要素が、自身の値を持ってくる先よりもっと先から値を持ってこようかをしてないかをチェックすればよい。
その後、逆向きにも同様にチェックする。

int Q,N;
int A[303030],B[303030];
int T[303030];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){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]=comp(v,val[entry]);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
	void set(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_1<int,1<<20> st;

int ok() {
	map<int,deque<int>> M;
	int i,x;
	FOR(i,N) M[B[i]].push_back(i);
	FOR(i,N) {
		if(M[A[i]].empty()) return 0;
		T[i]=M[A[i]].front();
		M[A[i]].pop_front();
	}
	
	int ret=1;
	FOR(i,N) {
		x=st.getval(0,A[i]);
		if(x>T[i]) ret=0;
		st.update(A[i],T[i]);
	}
	
	FOR(i,N) st.set(A[i],0);
	
	reverse(A,A+N);
	reverse(T,T+N);
	FOR(i,N) T[i]=N-1-T[i];
	
	FOR(i,N) {
		x=st.getval(A[i]+1,1<<19);
		if(x>T[i]) ret=0;
		st.update(A[i],T[i]);
	}
	
	FOR(i,N) st.set(A[i],0);
	
	return ret;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	FOR(i,Q) {
		cin>>N;
		FOR(j,N) cin>>A[j];
		FOR(j,N) cin>>B[j];
		if(ok()) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	
	
}

まとめ

ECR Dとしてはちょっと難しいかもね。
AC数見ても、Eと反対にしてよかったかも。