【题意】
有n个村庄进行m次操作,有三种操作
D x:表示摧毁一个村庄
Q x:表示查询一个村庄左右连续的存在的村庄个数,若该村庄不存在为0
R:表示修复上一个被摧毁的村庄
【输入】
第一行n,m
接下来m行每行表示一个命令
【输出】
对于每次查询输出答案
用线段树来描述一段区间内存在的村庄的个数
查询的时候首先判断当前村庄是否存在,不存在打0
若存在再二分左端点和右端点即可
program poj2892; var all,tot,n,m,i,j,k,x,s,e,ans,mid:longint; order:char; dl:array [0..100001] of longint; left,right,p:array [0..200001] of longint; procedure build (l,r:longint); begin inc(tot); left[tot]:=0; right[tot]:=0; p[tot]:=r-l+1; end; procedure insert (x,c,l,r,now:longint); begin p[now]:=p[now]+c; if l=r then exit; if x<=(l+r) div 2 then begin if left[now]=0 then begin build(l,(l+r) div 2); left[now]:=tot; end; insert(x,c,l,(l+r) div 2,left[now]); end else begin if right[now]=0 then begin build((l+r) div 2+1,r); right[now]:=tot; end; insert(x,c,(l+r) div 2+1,r,right[now]); end; end; function find (s,e,l,r,now:longint):longint; var k:longint; begin if (s=l)and(e=r) then exit(p[now]); if e<=(l+r) div 2 then if left[now]=0 then exit(e-s+1) else exit(find(s,e,l,(l+r) div 2,left[now])) else if s>(l+r) div 2 then if right[now]=0 then exit(e-s+1) else exit(find(s,e,(l+r) div 2 + 1,r,right[now])) else begin k:=0; if left[now]=0 then k:=k+(l+r) div 2-s+1 else k:=k+find(s,(l+r) div 2,l,(l+r) div 2,left[now]); if right[now]=0 then k:=k+e-(l+r) div 2 else k:=k+find((l+r) div 2+1,e,(l+r) div 2+1,r,right[now]); exit(k); end; end; begin readln(n,m); tot:=0; left[0]:=0; right[0]:=0; p[0]:=n; for i:=1 to m do begin read(order); case order of 'D':begin read(x); inc(all); dl[all]:=x; insert(x,-1,1,n,0); end; 'R':begin if all>0 then begin insert(dl[all],1,1,n,0); dec(all); end; end; 'Q':begin read(x); if find(x,x,1,n,0)=0 then writeln(0) else begin ans:=1; if (x-1>0)and(find(x-1,x-1,1,n,0)=1) then begin s:=1; e:=x-1; while s<>e do begin mid:=(s+e) div 2; if find(mid,x-1,1,n,0)=x-mid then e:=mid else s:=mid+1; end; ans:=ans+x-s; end; if (x+1<=n)and(find(x+1,x+1,1,n,0)=1) then begin s:=x+1; e:=n; while s<>e do begin mid:=s+e-(s+e) div 2; if find(x+1,mid,1,n,0)=mid-x then s:=mid else e:=mid-1; end; ans:=ans+s-x; end; writeln(ans); end; end; end; readln; end; end.