Codeforces #638 Div2 F. Phoenix and Memory

Hackされたのは惜しいけど、お蔭でACしたのでまぁいいか。
https://codeforces.com/contest/1348/problem/F

問題

1～Nの順列Aを考える。
i番目の要素はL[i]～R[i]の範囲でなければならないとする。

条件を満たす数列が1通りしかないか、2通り以上あるか求めよ。
2通り以上あるなら例を示せ。

解法

まず適当に1通り作ろう。
これは平面走査の要領で値の小さい順に、上限R[i]の小さい位置から優先的に埋めるようにしていくとよい。

次に、各要素について入れ替え可能な位置を考える。
今ある要素A[i]=xとする。A[i]はL[i]～R[i]の値が入っているので、x+1～R[i]が入っている他の場所jのうち、L[j]がx以下の箇所を探そう。
これは最小値を求めるSegTreeで対応できる。

template<class V,int NV> class SegTree_1 {
public:
	vector<pair<V,int>> val;
	static V const def=1<<30;
	pair<V,int> comp(pair<V,int> l,pair<V,int> r){ return min(l,r);};
	
	SegTree_1(){val=vector<pair<V,int>>(NV*2,make_pair(1<<30,0));};
	pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return make_pair(1<<30,0);
		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, pair<V,int> 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 N;
int L[202020],R[202020];
vector<int> add[202020];
vector<int> del[202020];
int A[202020],ret[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>L[i]>>R[i];
		L[i]--,R[i]--;
		add[L[i]].push_back(i);
	}
	
	set<pair<int,int>> Rs;
	FOR(i,N) {
		FORR(a,add[i]) Rs.insert({R[a],a});
		
		assert(Rs.size());
		
		A[i]=Rs.begin()->second;
		st.update(i,make_pair(L[A[i]],A[i]));
		Rs.erase(Rs.begin());
	}
	
	FOR(j,N) ret[A[j]]=j+1;
	FOR(i,N-1) {
		x=A[i];
		
		auto a=st.getval(i+1,R[x]+1);
		if(a.first<=i) {
			cout<<"NO"<<endl;
			FOR(j,N) cout<<ret[j]<<" ";
			cout<<endl;
			swap(ret[x],ret[a.second]);
			FOR(j,N) cout<<ret[j]<<" ";
			cout<<endl;
			return;
		}
		
	}
	
	cout<<"YES"<<endl;
	FOR(i,N) cout<<ret[i]<<" ";
	cout<<endl;
	
	
}

まとめ

最初もっと簡単な解法書いてHackされた。よく間に合ったな。