<题目链接>
题目大意：
一个长度为n的线段，下面m个操作
D x 表示将单元x毁掉
R 表示修复最后毁坏的那个单元
Q x 询问这个单元以及它周围有多少个连续的单元，如果它本身已经被毁坏了就是0。
解题分析：
用线段树求指定点所在的最长连续区间，属于线段树区间合并类型的题，线段树的每个节点需要维护三个值，分别是对应区间的最长连续区间长度，对应区间最长连续区间前缀，对应区间最长连续后缀，然后就是在每次update之后都维护一下这三个值就行。并且注意一下query 时的操作。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define Lson rt<<1,l,mid
#define Rson rt<<1|1,mid+1,r
const int N=+;
int len[N<<],llen[N<<],rlen[N<<];
int n,m; void Pushup(int rt,int length){ //更新维护每个节点的三个值
llen[rt]=llen[rt<<]; //首先当前节点的最长连续前缀==左子节点的最长连续前缀
rlen[rt]=rlen[rt<<|];
/*-- 进一步更新 --*/
if(llen[rt<<]==(length-(length>>)))llen[rt]+=llen[rt<<|]; //如果左子节点的最长连续前缀为整个左子区间，那么本节点的前缀还要加上右子区间的最长前缀
if(rlen[rt<<|]==(length>>))rlen[rt]+=rlen[rt<<]; //同理
/*-- 最终更新本节点的最长连续长度 --*/
len[rt]=max(max(len[rt<<],len[rt<<|]),rlen[rt<<]+llen[rt<<|]);
} void build(int rt,int l,int r){
if(l==r){
len[rt]=llen[rt]=rlen[rt]=;
return;
}
int mid=(l+r)>>;
build(Lson);
build(Rson);
Pushup(rt,r-l+);
} void update(int rt,int l,int r,int loc,int c){ //单点更新
if(l==r){
len[rt]=llen[rt]=rlen[rt]=c;
return;
}
int mid=(l+r)>>;
if(loc<=mid)update(Lson,loc,c);
if(loc>mid)update(Rson,loc,c);
Pushup(rt,r-l+);
} int query(int rt,int l,int r,int loc){
if(l==r)return len[rt];
int mid=(l+r)>>;
if(loc<=mid){
if(loc+rlen[rt<<]>mid)return rlen[rt<<]+llen[rt<<|]; //如果loc在左子区间的最长后缀和右子区间的最长前缀中，直接输出这两个前后缀之和即可
else return query(Lson,loc); //否则的话，继续向左子节点查询
}
else{
if(mid+llen[rt<<|]>=loc)return rlen[rt<<]+llen[rt<<|];//因为右子区间是(mid,r]左开区间，所以这里判断loc是否在右子区间的前缀的范围内用的是 ">="
else return query(Rson,loc);
}
} int main(){
while(scanf("%d %d",&n,&m)!=EOF){
build(,,n);
int tot=,stk[N+]; //stk模拟栈
while(m--){
char str[];
scanf("%s",str);
if(str[]=='D'){
int cal;scanf("%d",&cal);
stk[++tot]=cal;
update(,,n,cal,);
}
else if(str[]=='R'){
int cal=stk[tot--];
update(,,n,cal,);
}
else{
int cal;scanf("%d",&cal);
printf("%d\n",query(,,n,cal));
}
}
}
return ;
}
2018-09-23