Tunnel Warfare
思路：
这明明是单点查询，怎么说是区间合并呢？试问一下，题目要求是不是输出当前点连续的长度呢！！！
单点查询如何转换成区间查询？这就是题目的巧妙之处，查询的时候，在整个区间缩小为一个点的过程中，判断目标点是否在当前区间的连续区间内，如果在，我们再查询该连续区间的端点。（相当于感染）这样就可以查找到目标点所在的连续区间。
说的简单一点就是当前的点属于哪个较长的区间,这就不成区间查询了
首先是建树，在结构体里定义ls记录该区间左端点的最大连续个数，rs记录区间右端点开始的最大连续个数，ms表示该区间最大的连续个数。
#include<bits/stdc++.h>
using namespace std;
const int M=55000;
stack<int>s;
struct node
{
int l,r;
int ls,rs,ms;//ls从l开始左边最大连续，rs从r开始右边最大连续，整个l-s最长连续
} tree[M<<2];
void pushup(int root)
{
tree[root].ls=tree[root<<1].ls;//左连续
tree[root].rs=tree[root<<1|1].rs;//右连续
tree[root].ms=max(max(tree[root<<1].ms,tree[root<<1|1].ms),tree[root<<1].rs+tree[root<<1|1].ls);
//父亲区间内的最大区间必定是，左子树最大区间，右子树最大区间，左右子树连续区间合并的中间区间，三者中最大的区间值
if(tree[root<<1].ls==tree[root<<1].r-tree[root<<1].l+1)//说明左子树全部连续
{
tree[root].ls+=tree[root<<1|1].ls;//左子树区间满了的话，父亲左区间要加上右子树的左连续
}
if(tree[root<<1|1].rs==tree[root<<1|1].r-tree[root<<1|1].l+1)//说明右子树全部连续
{
tree[root].rs+=tree[root<<1].rs;//右子树区间满了的话，父亲右区间就要加上左子树的右连续
}
}
void build(int l,int r,int root)
{
tree[root].l=l;
tree[root].r=r;
tree[root].ls=tree[root].rs=tree[root].ms=r-l+1;
if(l!=r)
{
int mid=(l+r)>>1;
build(l,mid,root<<1);
build(mid+1,r,root<<1|1);
}
}
// void print(int l,int r,int root)
// {
// if(l==r)
// {
// printf("%d l %d\n",l,tree[root].ms);
// return ;
// }
// int mid=(l+r)>>1;
// print(l,mid,root<<1);
// print(mid+1,r,root<<1|1);
// }
void update(int root,int pos,int flag)
{
if(tree[root].l==tree[root].r)
{
if(flag==1)
{
tree[root].ls=tree[root].rs=tree[root].ms=1;//修复
}
else
{
tree[root].ls=tree[root].rs=tree[root].ms=0;//摧毁
}
return ;
}
int mid=(tree[root].l+tree[root].r)>>1;
if(pos<=mid)
{
update(root<<1,pos,flag);
}
else
{
update(root<<1|1,pos,flag);
}
pushup(root);
}
int query(int root,int pos)
{
if(tree[root].l==tree[root].r||tree[root].ms==0||tree[root].ms==tree[root].r-tree[root].l+1)
{
return tree[root].ms;//到了叶子节点或者该访问区间为空或者已满都不必要往下走了
}
int mid=(tree[root].l+tree[root].r)>>1;
if(pos<=mid)
{
if(pos>=tree[root<<1].r-tree[root<<1].rs+1)//因为pos<=mid，看左子树，tree[root<<1].r-tree[root<<1].rs+1代表左子树右连续区间的左边界值，如果pos在左子树的右连续内，则要看右子树的左连续有多长并返回
{
return query(root<<1,pos)+query(root<<1|1,mid+1);
}
else
{
return query(root<<1,pos);//如果不在左子树的右连续区间内，则只需要看左子树
}
}
else
{
if(pos<=tree[root<<1|1].l+tree[root<<1|1].ls-1)//因为pos>mid，看右子树,tree[root<1|1].l+tree[root<<1|1].ls-1代表右子树左连续区间的右边界值，如果pos在右子树的左连续内，则要看左子树的右连续有多长
{
return query(root<<1|1,pos)+query(root<<1,mid);
}
else
{
return query(root<<1|1,pos);//如果不在右子树的左连续区间内，则只需要看右子树
}
}
}
int main( )
{
int n,q,x;
char str[2];
while(~scanf("%d%d",&n,&q))
{
while(!s.empty( ))
{
s.pop( );
}
build(1,n,1);
//print(1,n,1);
while(q--)
{
cin>>str;
if(str[0]=='D')
{
cin>>x;
s.push(x);
update(1,x,0);
//print(1,n,1);
}
if(str[0]=='Q')
{
cin>>x;
cout<<query(1,x)<<endl;
}
if(str[0]=='R'&&!s.empty( ))
{
x=s.top( );
s.pop( );
update(1,x,1);
//print(1,n,1);
}
}
}
return 0;
}
