【题意】D代表破坏村庄,R代表修复最后被破坏的那个村庄,Q代表询问包括x在内的最大连续区间是多少?
【解题方法】很基础的线段树区间维护了,lsum代表区间左端点开始的最大连续值,rsum代表区间右端点开始的最大连续值,msum代表整个区间的最大连续值!
【AC 代码】
//HDU 1540
//Tunnel Warfare.
#include <bits/stdc++.h>
using namespace std;
const int maxn=50010;
int s[maxn],top;
struct node{
int l,r;
int lsum,rsum,msum;
}Tree[maxn<<2];
void PushUp(int rt)
{
Tree[rt].lsum=Tree[rt*2].lsum;
Tree[rt].rsum=Tree[rt*2+1].rsum;
Tree[rt].msum=max(max(Tree[rt*2].msum,Tree[rt*2+1].msum),Tree[rt*2].rsum+Tree[rt*2+1].lsum);
if(Tree[rt*2].lsum==Tree[rt*2].r-Tree[rt*2].l+1) Tree[rt].lsum+=Tree[rt*2+1].lsum;
if(Tree[rt*2+1].rsum==Tree[rt*2+1].r-Tree[rt*2+1].l+1) Tree[rt].rsum+=Tree[rt*2].rsum;
}
void Build(int l,int r,int rt)
{
Tree[rt].l=l,Tree[rt].r=r;
Tree[rt].lsum=Tree[rt].rsum=Tree[rt].msum=r-l+1;
if(l==r) return ;
int m=(l+r)/2;
Build(l,m,rt*2);
Build(m+1,r,rt*2+1);
}
void update(int pos,int val,int rt)
{
if(Tree[rt].l==Tree[rt].r)
{
if(val==1) Tree[rt].lsum=Tree[rt].rsum=Tree[rt].msum=1;
else Tree[rt].lsum=Tree[rt].rsum=Tree[rt].msum=0;
return ;
}
int mid=(Tree[rt].l+Tree[rt].r)/2;
if(pos<=mid) update(pos,val,rt*2);
else update(pos,val,rt*2+1);
PushUp(rt);
}
int query(int rt,int pos)
{
if(Tree[rt].l==Tree[rt].r||Tree[rt].msum==0||Tree[rt].msum==Tree[rt].r-Tree[rt].l+1) return Tree[rt].msum;
int mid=(Tree[rt].l+Tree[rt].r)/2;
if(pos<=mid)
{
if(pos>=Tree[rt*2].r-Tree[rt*2].rsum+1)
return query(rt*2,pos)+query(rt*2+1,mid+1);
else
return query(rt*2,pos);
}
else
{
if(pos<=Tree[rt*2+1].l+Tree[rt*2+1].lsum-1)
return query(rt*2+1,pos)+query(rt*2,mid);
else
return query(rt*2+1,pos);
}
}
int main()
{
int n,q,x;
char op[3];
while(~scanf("%d%d",&n,&q))
{
top=0;
Build(1,n,1);
//puts("success");
for(int i=1; i<=q; i++)
{
scanf("%s",op);
if(op[0]=='D')
{
scanf("%d",&x);
s[top++]=x;
update(x,0,1);
}
else if(op[0]=='Q')
{
scanf("%d",&x);
printf("%d\n",query(1,x));
}
else
{
if(x>0){
x=s[--top];
update(x,1,1);
}
}
}
}
}