hdu1540 線段樹區間合並

hdu1540 線段樹區間合並

先說下題意：

有連續的n個村莊編號1--n 開始相鄰的能連續上 現在執行m次操作

1：毀壞村莊a

2：詢問與a能連續的村莊的個數

3：修好最後被毀壞的村莊（此處用到棧 注意多次毀壞同一村莊的情況）

整天還是線段樹做 對每個節點存3個值

pre ：左端點連續個數

after ：右端點連續個數

Max：整個區間連續個數

跟新操作分為毀壞和維修 用-1和1區別

這道題與別的不同在於他的點詢問 可以根據Max來判斷

#include
#include
#include
#include
#include
using namespace std;

#define LL(x) (x<<1)
#define RR(x) ((x<<1)|1)


struct node
{
    int pre,after,Max;
}num[4*50000];
int max(int a,int b)
{
    return a>b?a:b;
}
int deal(int L,int R,int mark)
{
    int mid=(L+R)/2;
    num[mark].pre=num[mark].after=num[mark].Max=R-L+1;
    if(L==R) return 0;
    deal(L,mid,LL(mark));
    deal(mid+1,R,RR(mark));
    return 0;            
}
int update(int L,int R,int pos,int mark,int k)
{
    if(L==R&&L==pos)
    {
        if(k==-1)
        num[mark].pre=num[mark].after=num[mark].Max=0;
        else
        num[mark].pre=num[mark].after=num[mark].Max=1;
        return 0;
    }    
    int mid=(L+R)/2;
    if(pos<=mid)
    update(L,mid,pos,LL(mark),k);
    else update(mid+1,R,pos,RR(mark),k);
    num[mark].pre=num[LL(mark)].pre;
    if(num[LL(mark)].pre==mid-L+1)
    num[mark].pre+=num[RR(mark)].pre;
    num[mark].after=num[RR(mark)].after;
    if(num[RR(mark)].after==R-mid) 
    num[mark].after+=num[LL(mark)].after;
    num[mark].Max=max(num[LL(mark)].Max,num[RR(mark)].Max);
    num[mark].Max=max(num[mark].Max,num[LL(mark)].after+num[RR(mark)].pre);
    return 0;
}
int find(int L,int R,int pos,int mark)
{
    if(num[mark].Max==R-L+1||num[mark].Max==0||L==R)
    {
        return num[mark].Max;
    }
    int mid=(L+R)/2;
    if(pos<=mid)
    {
        if(pos>=mid-num[LL(mark)].after)
        return find(L,mid,pos,LL(mark))+num[RR(mark)].pre;
        else return find(L,mid,pos,LL(mark));
    }    
    else
    {
        if(pos<=num[RR(mark)].pre+mid+1)
        return find(mid+1,R,pos,RR(mark))+num[LL(mark)].after;
        else return find(mid+1,R,pos,RR(mark));
    }
}
int main()
{
    int n,m,i,j,a;
    int leap[50010];
    char str[5];
    while(~scanf("%d%d",&n,&m))
    {
        deal(1,n,1);
        stackq;
        memset(leap,0,sizeof(leap));
        for(i=1;i<=m;i++)
        {
            scanf("%s",str);
            if(str[0]=='D')
            {
                scanf("%d",&a);    
                q.push(a);
                if(leap[a]==0)
                {
                    leap[a]=1;
                    update(1,n,a,1,-1);
                }
            }
            else if(str[0]=='R')
            {
                int b;
                while(!q.empty())
                {
                    b=q.top();
                    q.pop();
                    if(leap[b]==1) 
                    {
                        leap[b]=0;
                        update(1,n,b,1,1);
                        break;
                    }
                }
            }
            else
            {
                scanf("%d",&a);
                if(leap[a]==1) printf("0\n");
                else printf("%d\n",find(1,n,a,1));
            }        
        }
    }
    return 0;    
}