题目大意给你一个01串就是求每个点的最长连续值为1的区间的长度，我们可以将村庄抽象成一个点，正常下值为1,被破坏后变成0,即可将题目抽象成一个求目标节点所在的最长连续1序列的区间的长度。
这题用的是线段树区间合并的方法。对每个区间我们维护5个值l，r，lsum表示从区间的l开始的连续1的长度，rsum相同，msum表示l到r区间最长的连续1的长度。
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn=500005;
#define ls i<<1
#define rs (i<<1)|1
struct node
{
int l,r;
int lsum,rsum,msum;
}tree[maxn<<2];
int istack[maxn],top=0;
void pushup(int i)
{
tree[i].lsum=tree[ls].lsum;
tree[i].rsum=tree[rs].rsum;
if(tree[i].lsum==(tree[ls].r-tree[ls].l+1))
tree[i].lsum+=tree[rs].lsum;
if(tree[i].rsum==(tree[rs].r-tree[rs].l+1))
tree[i].rsum+=tree[ls].rsum;
tree[i].msum=max(max(tree[ls].rsum+tree[rs].lsum,tree[i].lsum),tree[i].rsum);
}
void build(int i,int l,int r)
{
tree[i].l=l;
tree[i].r=r;
if(l==r)
{
tree[i].lsum=tree[i].rsum=tree[i].msum=1;
return ;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(i);
}
void update(int i,int op,int pos)
{
if(tree[i].l==tree[i].r)
{
tree[i].lsum=tree[i].rsum=tree[i].msum=op;
return ;
}
int mid=(tree[i].l+tree[i].r)>>1;
if(pos<=mid)
update(ls,op,pos);
else
update(rs,op,pos);
pushup(i);
}
int query(int i,int pos)
{
if((tree[i].l==tree[i].r)||(tree[i].msum==(tree[i].r-tree[i].l+1))||(tree[i].msum==0)) return tree[i].msum;
int mid = (tree[i].l+tree[i].r)>>1;
if(pos<=mid)//满足则在左儿子找
{
if(pos>=(tree[ls].r-tree[ls].rsum+1))
return query(ls,pos)+query(rs,mid+1);
else
return query(ls,pos);
}
else
if(pos<=(tree[rs].lsum+tree[rs].l-1))
return query(rs,pos)+query(ls,mid);
else
return query(rs,pos);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
build(1,1,n);
//cout<<"***************"<<endl;
//cout<<"l r lsum rsum msum"<<endl;
//for(int i=1;i<=7;i++)
//cout<<i<<"节点的值"<<tree[i].l<<" "<<tree[i].r<<" "<<tree[i].lsum<<" "<<tree[i].rsum<<" "<<tree[i].msum<<endl;
int pos;
char ch[10];
while(m--)
{
scanf("%s",ch);
if(ch[0]=='D')
{
scanf("%d",&pos);
istack[++top]=pos;
update(1,0,pos);
//cout<<"***************"<<endl;
//cout<<"l r lsum rsum msum"<<endl;
//for(int i=1;i<=7;i++)
//cout<<i<<"节点的值"<<tree[i].l<<" "<<tree[i].r<<" "<<tree[i].lsum<<" "<<tree[i].rsum<<" "<<tree[i].msum<<endl;
}
else
if(ch[0]=='R')
{
if(!top) continue;
pos=istack[top--];
update(1,1,pos);
}
else
{
scanf("%d",&pos);
printf("%d
",query(1,pos));
}
}
}
return 0;
}