Codeforces #773 : Div1 C. Anonymity Is Important

割と苦戦してるな。
https://codeforces.com/contest/1641/problem/C

問題

N人の人がいて、それぞれ病気かそうでないかのいずれかである。
ただし、初期状態で各人がどちらであるかは不明である。
下記クエリを処理せよ。

• ある人の区間内[L,R]に、病気の人が0人か1人以上かの情報が与えられる。
• 指定された人Jが、病気確定か、病気でないこと確定か、いずれか未確定かを答えよ。

解法

以下の2つの情報を管理しよう。

• 病気の可能性がある人の番号をset Sで管理
• f(X) := [X,f(X)]の区間の間に少なくとも1人は病気の人がいるような最小の値

まず後者のクエリを処理する。

• J∉Sなら、Jは病気でないこと確定。
• J∈Sなら、[J,f(J)]の範囲にJ以外の病気の可能性の人がいないなら、Jは病気確定。そうでないなら、未確定。

前者のクエリに対しては以下のように処理する。

• 病気の人が区間内にいない場合、Sから区間内の人を取り除く。その際、取り除いた人の番号vに対し、f(v)を次の病気の可能性がある人wに対するf(w)に伝搬させる。
• 病気の人が区間内にいる場合、Sの中で[L,R]内で病気の可能性がある人の最小の番号vに対し、f(v)をRで更新する。

int N,Q;
set<int> alive;
int Rlimit[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&Q);
	FOR(i,N+2) alive.insert(i), Rlimit[i]=N+1;
	
	while(Q--) {
		scanf("%d",&x);
		int L,R,X;
		if(x==0) {
			scanf("%d%d%d",&L,&R,&X);
			
			if(X==0) {
				while(1) {
					auto it=alive.lower_bound(L);
					x=*it;
					if(x>R) break;
					y=*next(it);
					if(y<=Rlimit[x]) Rlimit[y]=min(Rlimit[x],Rlimit[y]);
					alive.erase(it);
				}
			}
			else {
				auto it=alive.lower_bound(L);
				Rlimit[*it]=min(Rlimit[*it],R);
			}
			
		}
		else {
			scanf("%d",&X);
			if(alive.count(X)==0) {
				cout<<"NO"<<endl;
			}
			else {
				auto it=alive.find(X);
				if(*next(it)<=Rlimit[X]) {
					cout<<"N/A"<<endl;
				}
				else {
					cout<<"YES"<<endl;
				}
			}
			
		}
	}
	
}

まとめ

ありそうな設定だけど、意外にこれまで見たことなかったな。