Codeforces #1018 : F. Wonderful Impostors

シンプルな問題設定ながら割と手間取った。
https://codeforces.com/contest/2096/problem/F

問題

M個の真偽値を取る変数と、N個の情報がある。
各情報iは、以下のいずれかの形をとる。

• 区間[A[i],B[i]]の範囲の変数に、trueを取るものはない
• 区間[A[i],B[i]]の範囲の変数に、少なくとも1個はtrueを取るものがある

クエリとして、情報の区間が与えられる。
各情報をすべて満たすような真偽値の割り当てが存在するか判定せよ。

解法

クエリとして指定される区間が長くなるほど、真偽値の割り当ては難しくなる。
よってあらかじめ区間の左端に対し、尺取り法の要領で条件を満たす右端を求めよう。

後者のタイプの情報の区間のうち、前者のタイプの区間の組み合わせですべて覆われてしまうケースがある場合、それらの情報群は条件を満たさない。
これをSegTreeを使って差分更新していこう。

int T,N,M;
int X[202020],A[202020],B[202020];
int Q;
int ret[202020];

static ll const def=0;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		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 || y<=x) return 1<<20;
		if(val[k]) return 1;
		if(x<=l && r<=y) return ma[k];
		return val[k]+min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r||y<=x) 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]=val[k]+min(ma[k*2],ma[k*2+1]);
		}
	}
};
SegTree_3<int,1<<18> cover;

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

multiset<int> P[1<<18];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,1<<18) {
		P[i].insert(1<<18);
		mi.update(i,1<<18);
	}
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,M) {
			cin>>X[i]>>A[i]>>B[i];
			A[i]--;
		}
		
		for(int L=0,R=0;L<M;L++) {
			while(R<M) {
				if(X[R]==0) {
					int CL=A[R],CR=B[R];
					cover.update(A[R],B[R],1);
					for(i=20;i>=0;i--) {
						if(CL-(1<<i)>=0&&cover.getval(CL-(1<<i),CR)>0) CL-=1<<i;
						if(CR+(1<<i)<=N&&cover.getval(CL,CR+(1<<i))>0) CR+=1<<i;
					}
					if(mi.getval(CL,CR)<=CR) {
						cover.update(A[R],B[R],-1);
						break;
					}
				}
				else {
					if(cover.getval(A[R],B[R])>0) break;
					P[A[R]].insert(B[R]);
					mi.update(A[R],*P[A[R]].begin());
				}
				R++;
			}
			ret[L]=R;
			if(X[L]==0) {
				cover.update(A[L],B[L],-1);
			}
			else {
				P[A[L]].erase(P[A[L]].find(B[L]));
				mi.update(A[L],*P[A[L]].begin());
			}
		}
		cin>>Q;
		while(Q--) {
			cin>>x>>y;
			x--;
			if(ret[x]>=y) {
				cout<<"YES"<<"\n";
			}
			else {
				cout<<"NO"<<"\n";
			}
		}
		
	}
}

まとめ

考え方はシンプルだけど、細かい実装が結構面倒。