题意: 最初1-2-3-…-n按照顺序每个点与相邻的和两点相连成一条链。 三种操作D: 毁掉x R: 恢复上次毁掉的 Q:查询与x直接相连或者间接相邻的数量(包括自己) 题目类型：线段树求区间连续最大和的模板题目 思路： 维护区间从左端点开始最大连续个数lsum， 以及当前区间从右端点开始最大连续的个数rsum。重点push_up（）函数的写法。
查询的时候 查看当前点是否在子区间的rsum和lsum 范围内，是的话答案就是它。找不到就是0。用栈来维护被摧毁的城市。
#include<bits/stdc++.h> using namespace std; #define root 1,n,1 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int N=5e4+10; int lsum[N<<2],rsum[N<<2],sta[N],n,q; void push_up(int rt,int m){ lsum[rt]=lsum[rt<<1]; rsum[rt]=rsum[rt<<1|1]; if(lsum[rt<<1]==m-(m>>1)) lsum[rt]+=lsum[rt<<1|1]; if(rsum[rt<<1|1]==m>>1) rsum[rt]+=rsum[rt<<1]; } void build(int l,int r,int rt){ lsum[rt]=rsum[rt]=r-l+1; if(l==r) return; int m=l+r >>1; build(l,m,rt<<1); build(m+1,r,rt<<1|1); } void update(int o,int v,int l,int r,int rt){ if(l==r){ lsum[rt]=rsum[rt]=v; return; } int m=l+r>>1; if(o<=m) update(o,v,lson); else update(o,v,rson); push_up(rt,r-l+1); } int query(int o,int l,int r,int rt){ if(l==r) return 0; int m=l+r >>1; if(o>=m-rsum[rt<<1]+1&&o<=m+lsum[rt<<1|1]){ return rsum[rt<<1]+lsum[rt<<1|1]; } if(o<=m) return query(o,lson); else return query(o,rson); } int main(){ while(~scanf("%d%d",&n,&q)){ build(root); int t=0; while(q--){ char op[2];scanf("%s",op); if(op[0]=='R'){ int x=sta[--t]; update(x,1,root); } else{ int x;scanf("%d",&x); if(op[0]=='D'){ update(x,0,root); sta[t++]=x; } else printf("%d\n",query(x,root)); } } } }