题意:
D x 表示摧毁一个村庄
Q x 表示查询第x个村庄左右连续的地道数(包括自身)
R 表示修复上一个被摧毁的村庄
思路:
线段树的区间合并,用栈保存摧毁的村庄。
查询的时候可以这样,先查询[1,x]的地道数,如果为0,结果为0。如果不为0,则加上[x+1,n]的左节点往右的最大连续数。
#include<stdio.h> #define max(a,b) (a>b?a:b) #define min(a,b) (a<b?a:b) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn = 50100; int stack[maxn],top; int lsum[maxn<<2],rsum[maxn<<2],msum[maxn<<2]; void pushup(int rt,int m) { lsum[rt]=lsum[rt<<1]; rsum[rt]=rsum[rt<<1|1]; if(lsum[rt]==m-(m>>1)) lsum[rt]+=lsum[rt<<1|1]; if(rsum[rt]==(m>>1)) rsum[rt]+=rsum[rt<<1]; msum[rt]=max(lsum[rt<<1|1]+rsum[rt<<1],max(msum[rt<<1],msum[rt<<1|1])); } void build(int l,int r,int rt) { msum[rt]=lsum[rt]=rsum[rt]=r-l+1; if(l==r) return; int m=(l+r)>>1; build(lson); build(rson); } void update(int P,int c,int l,int r,int rt) { if(P==l&&P==r) { lsum[rt]=rsum[rt]=msum[rt]=c; return; } else if(l==r) return; int m=(l+r)>>1; if(P<=m) update(P,c,lson); else update(P,c,rson); pushup(rt,r-l+1); } int query(int L,int R,int P,int l,int r,int rt) { if(L<=l&&r<=R) { if(l<=P) return rsum[rt]; else return lsum[rt]; } int m=(l+r)>>1; int la=0,ra=0; if(m>=R) return query(L,R,P,lson); else if(L>m) return query(L,R,P,rson); else { la=query(L,m,P,lson); ra=query(m+1,R,P,rson); int t=min(r-l+1,r-L+1); if(R<=P) { t=min(R-m,r-m); if(ra==t) return la+ra; else return ra; } else { t=min(m-l+1,m-L+1); if(la==t) return la+ra; else return la; } } } int main() { int n,m,a; char s[10]; while(scanf("%d%d",&n,&m)!=EOF) { top=0; build(1,n,1); while(m--) { scanf("%s",s); if(s[0]=='D') { scanf("%d",&a); stack[++top]=a; update(a,0,1,n,1); } else if(s[0]=='R') { a=stack[top--]; update(a,1,1,n,1); } else { scanf("%d",&a); int la=0,ra=0; la=query(1,a,a,1,n,1); if(a<n) ra=query(a+1,n,a,1,n,1); printf("%d\n",la?la+ra:0); } } } return 0; }