sgu-263 Towers

sgu-263 Towers

題目大意：

從1～106有106個基底，一開始上面都沒有積木，高度為0，連續的一段高度大於0的基底算作一個tower，顯然一開始tower數為0。
接下來有兩個操作：
1.put x c 將c個積木放在第x個基底上。
2.tput t x c 將c個積木放在第t個tower中的第x個基底上(tower從左到右排列並且保證存在這個基底)。
然後有四個詢問：
1.towers 問當前有多少個tower。
2.cubes t 問第t個tower一共有多少個積木。
3.length t 問第t個tower包含了多少個基底，即寬度是多少。
4.tcube t x 問第t個tower的第x個基底上有多少個積木。

解題思路：

平衡樹的裸題(好像有線段樹的做法，但是我不會啊QAQ)。
我們建一個平衡樹維護tower，記錄一下左端點、右端點、和一共有多少個積木，每次增加積木時，如果當前的基底上沒有積木，那麼就考慮是否會新增一個tower，或者擴大一個tower，或者是合並兩個tower。總的來說還是很簡單的。

AC代碼:

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int QAQ;

struct tree_
{
    int son[2],fa,Size,left,right,cubes;
    inline void clear()
    {son[0]=son[1]=fa=Size=left=right=cubes=0;}
}tower[1000010];
int tower_end=0;
int root;
int height[1000010]={0};

inline void read_(int &x)
{
    x=0;
    char ch=getchar();
    for(;ch=='\n' || ch=='\r' || ch==' ';ch=getchar());
    for(;ch>='0' && ch<='9';ch=getchar())
        x=x*10+ch-'0';
    return;
}

void rotate(int k)
{
    int Fa=tower[k].fa;
    int g=(tower[Fa].son[1]==k);
    tower[k].fa=tower[Fa].fa;
    tower[k].Size=tower[Fa].Size;
    if(tower[k].son[g^1]!=0) tower[tower[k].son[g^1]].fa=Fa;
    tower[Fa].Size=tower[tower[Fa].son[g^1]].Size+tower[tower[k].son[g^1]].Size+1;
    tower[Fa].son[g]=tower[k].son[g^1];
    tower[Fa].fa=k;
    tower[k].son[g^1]=Fa;
    if(tower[k].fa!=0)
    {
        g=(tower[tower[k].fa].son[1]==tower[k].son[g^1]);
        tower[tower[k].fa].son[g]=k;
    }
    return;
}

inline void splay(int k)
{

    for(;tower[k].fa!=0;)
    {
        if(tower[k].fa==root)
            rotate(k);
        else
        {
            int Fa=tower[k].fa;
            int g1=(tower[tower[k].fa].son[1]==k);
            int g2=(tower[tower[Fa].fa].son[1]==Fa);
            if(g1==g2)
            {
                rotate(Fa);
                rotate(k);
            }
            else
            {
                rotate(k);
                rotate(k);
            }
        }
    }
    root=k;
    return;
}

inline int Findtower(int k,int now)
{
    int l=tower[now].son[0];
    int r=tower[now].son[1];
    if(tower[l].Size>=k)
        return Findtower(k,l);
    if(tower[l].Size+1k) return Findtower2(k,tower[now].son[0]);
    if(tower[now].right0;QAQ--)
    {
        char ch[10]="\0";

        scanf("%s",ch);
        if(strcmp("put",ch)==0)
        {
            int x,c;
            read_(x),read_(c);
            if(height[x]!=0)
            {
                int tt=Findtower2(x,root);
                tower[tt].cubes+=c;
            }
            else
            {
                if(height[x-1]==0 && height[x+1]==0)
                {
                    int tt;
                    if(root==0)
                    {
                        tt=++tower_end;
                        tower[tt].left=tower[tt].right=x;
                        tower[tt].Size=1;
                        root=tt;
                    }
                    else
                    {
                        tt=Add(x,root);
                        splay(tt);
                    }
                    tower[tt].cubes+=c;
                }
                else if((height[x-1]>0)+(height[x+1]>0)==1)
                {
                    int xx=height[x-1]>0?x-1:x+1;
                    int tt=Findtower2(xx,root);
                    tower[tt].cubes+=c;
                    if(xx==x-1) tower[tt].right=x;
                    else tower[tt].left=x;
                    splay(tt);
                }
                else
                {
                    int tt1=Findtower2(x-1,root);
                    int tt2=Findtower2(x+1,root);
                    splay(tt2);splay(tt1);
                    tower[tt1].cubes+=tower[tt2].cubes+c;
                    tower[tt1].right=tower[tt2].right;
                    tower[tt1].son[1]=tower[tt2].son[1];
                    tower[tt1].Size--;
                    if(tower[tt2].son[1]!=0)
                        tower[tower[tt2].son[1]].fa=tt1;
                    tower[tt2].clear();
                }
            }
            height[x]+=c;
        }
        else if(strcmp("tput",ch)==0)
        {
            int t,x,c;
            read_(t);
            //scanf("%d",&t);
            t=Findtower(t,root);
            read_(x),read_(c);
        //  scanf("%d%d",&x,&c);
            height[tower[t].left+x-1]+=c;
            tower[t].cubes+=c;
            splay(t);
        }
        else if(strcmp("towers",ch)==0)
            printf("%d towers\n",tower[root].Size);
        else if(strcmp("cubes",ch)==0)
        {
            int t;
            read_(t);
            //scanf("%d",&t);
            int tt=Findtower(t,root);
            splay(tt);
            printf("%d cubes in %dth tower \n",tower[tt].cubes,t);
        }
        else if(strcmp("length",ch)==0)
        {
            int t;
            read_(t);
            //scanf("%d",&t);
            int tt=Findtower(t,root);
            splay(tt);
            printf("length of %dth tower is %d\n",t,tower[tt].right-tower[tt].left+1);
        }
        else if(strcmp("tcubes",ch)==0)
        {
            int t,x;
            read_(t),read_(x);
            //scanf("%d%d",&t,&x);
            int tt=Findtower(t,root);
            splay(tt);
            printf("%d cubes in %dth column of %dth tower\n",height[tower[tt].left+x-1],x,t);
        }
    }
    return 0;
}