2892 Tunnel Warfare

問題概要

n個の村が一列に並んでいる。
次のようなm個のクエリを処理せよ。

D x
x番目の村が日本軍によって破壊される。
Q x
x番目の村から左右につながる、破壊されていない村の長さを出力。ただしその村自身が破壊されているときは0を出力。
R
最後に破壊された村が再建する。

n,m≦50000とする。

解法

村の連なりを愚直に判定するとおそらくTLE.
ここでは次のようにBinary Indexed Treeを使って、D,RのクエリをO(log n),
QのクエリをO((log n)^2)で処理した。


i番目の村が破壊されたときに、BITのi番目に1を足す。再建したときは-1.
村のつながりを見るときは、(今の村のBITの値-1)と(今の村のBITの値+1)が最初に出てくる場所を二分探索で探す。

ソースコード

int n,m,bit[50003],in[50000],k;
int sum(int i){
	int s=0;
	for(;i>0;i-=i&-i)s+=bit[i];
	return s;
}
void add(int i,int x){
	for(;i<=n;i+=i&-i)bit[i]+=x;
}
void func(int t){
	int lo=0,hi=t,mid,tmp,cur=sum(t);
	while(lo+1<hi){
		mid=(lo+hi)/2;
		if(sum(mid)<cur)lo=mid; else hi=mid;
	}
	if(hi==t){
		puts("0"); return;
	}
	tmp=hi; lo=t; hi=n;
	while(lo+1<hi){
		mid=(lo+hi)/2;
		if(sum(mid)<=cur)lo=mid; else hi=mid;
	}
	printf("%d\n",lo-tmp);
}

int main(){
	scanf("%d%d",&n,&m); n+=2;
	add(1,1); add(n,1);
	
	char c;
	rep(i,m){
		scanf(" %c",&c);
		if(c=='R')add(in[--k],-1);
		else{
			int t; scanf("%d",&t); t++;
			if(c=='D'){
				in[k++]=t;
				add(t,1);
			}
			else func(t);
		}
	}
	return 0;
}