HDU 4553 線段樹雙關鍵字區間合並

HDU 4553 線段樹雙關鍵字區間合並

用兩個關鍵字記錄，分別為屌絲時間和女神時間

若屌絲約，更新屌絲時間

若女神約，更新屌絲和女神時間

學習，則兩個全部清空

#include "stdio.h"
#include "string.h"

struct Data
{
    int l,r,x1,x2,l1,l2,r1,r2;
}data[400010];

int Max(int a,int b)
{
    if (a=x) return data[k].l;
        if (data[k*2].x1>=x) return query(x,k*2,op);
        if (data[k*2].r1+data[k*2+1].l1>=x) return data[k*2].r-data[k*2].r1+1;
        return query(x,k*2+1,op);
    }
    if (op==2)
    {
        if (data[k].x2=x) return data[k].l;
        if (data[k*2].x2>=x) return query(x,k*2,op);
        if (data[k*2].r2+data[k*2+1].l2>=x) return data[k*2].r-data[k*2].r2+1;
        return query(x,k*2+1,op);
    }
}

void Pushdown(int k)
{
    int ll,rr,sum;
    if (data[k].l==data[k].r) return ;
    ll=data[k*2].r-data[k*2].l+1;
    rr=data[k*2+1].r-data[k*2+1].l+1;
    sum=data[k].r-data[k].l+1;
    if (data[k].x1==0)
    {
        data[k*2].x1=data[k*2].l1=data[k*2].r1=0;
        data[k*2+1].x1=data[k*2+1].l1=data[k*2+1].r1=0;
    }
    if (data[k].x1==sum)
    {
        data[k*2].x1=data[k*2].l1=data[k*2].r1=ll;
        data[k*2+1].x1=data[k*2+1].l1=data[k*2+1].r1=rr;
    }
    if (data[k].x2==0)
    {
        data[k*2].x2=data[k*2].l2=data[k*2].r2=0;
        data[k*2+1].x2=data[k*2+1].l2=data[k*2+1].r2=0;
    }
    if (data[k].x2==sum)
    {
        data[k*2].x2=data[k*2].l2=data[k*2].r2=ll;
        data[k*2+1].x2=data[k*2+1].l2=data[k*2+1].r2=rr;
    }
}

void Pushup(int k)
{
    int ll,rr;
    ll=data[k*2].r-data[k*2].l+1;
    rr=data[k*2+1].r-data[k*2+1].l+1;

    data[k].l1=data[k*2].l1;
    if (data[k].l1==ll) data[k].l1+=data[k*2+1].l1;
    data[k].r1=data[k*2+1].r1;
    if (data[k].r1==rr) data[k].r1+=data[k*2].r1;
    data[k].x1=Max(Max(data[k*2].x1,data[k*2+1].x1),data[k*2].r1+data[k*2+1].l1);
    data[k].x1=Max(Max(data[k].l1,data[k].r1),data[k].x1);

    data[k].l2=data[k*2].l2;
    if (data[k].l2==ll) data[k].l2+=data[k*2+1].l2;
    data[k].r2=data[k*2+1].r2;
    if (data[k].r2==rr) data[k].r2+=data[k*2].r2;
    data[k].x2=Max(Max(data[k*2].x2,data[k*2+1].x2),data[k*2].r2+data[k*2+1].l2);
    data[k].x2=Max(Max(data[k].l2,data[k].r2),data[k].x2);
}
void updata(int l,int r,int k,int op)
{
    int mid,sum;
    if (data[k].l==l && data[k].r==r)
    {
        sum=data[k].r-data[k].l+1;
        if (op==0)
        {
            data[k].x1=data[k].l1=data[k].r1=sum;
            data[k].x2=data[k].l2=data[k].r2=sum;
            return ;
        }
        if (op==1)
        {
            data[k].x1=data[k].l1=data[k].r1=0;
            return ;
        }
        if (op==2)
        {
            data[k].x1=data[k].l1=data[k].r1=0;
            data[k].x2=data[k].l2=data[k].r2=0;
            return ;
        }
    }

    Pushdown(k);

    mid=(data[k].l+data[k].r)/2;

    if (r<=mid) updata(l,r,k*2,op);
    else
        if (l>mid) updata(l,r,k*2+1,op);
    else
    {
        updata(l,mid,k*2,op);
        updata(mid+1,r,k*2+1,op);
    }
    Pushup(k);
}
int main()
{
    int T,Case,x,y,start,n,m;
    char ch[10];
    scanf("%d",&T);
    Case=0;
    while (T--)
    {
        Case++;
        printf("Case %d:\n",Case);
        scanf("%d%d",&n,&m);
        build(1,n,1);
        while (m--)
        {
            scanf("%s",ch);
            if (ch[0]=='D')
            {
                scanf("%d",&x);
                start=query(x,1,1); // 詢問是否有連續x的屌絲時間
                if (start==0)
                    printf("fly with yourself\n");
                else
                {
                    updata(start,start+x-1,1,1); // 從start開始連續x個，更新屌絲時間
                    printf("%d,let's fly\n",start);
                }
            }
            else
            if (ch[0]=='N')
            {
                scanf("%d",&x);
                start=query(x,1,1);
                if (start!=0)
                {
                    updata(start,start+x-1,1,2);
                    printf("%d,don't put my gezi\n",start);
                    continue;
                }
                start=query(x,1,2);// 詢問是否有連續x的女神時間
                if (start!=0)
                {
                    updata(start,start+x-1,1,2); // 從start開始連續x個，更新屌絲和女神時間
                    printf("%d,don't put my gezi\n",start);
                    continue;
                }
                printf("wait for me\n");
            }
            else
            {
                scanf("%d%d",&x,&y);
                updata(x,y,1,0); // 更新學習時間
                printf("I am the hope of chinese chengxuyuan!!\n");
            }
        }

    }
    return 0;
}