bzoj 1208 splayストレッチツリー

splay伸展樹は主に2種類の操作形式(1)正常な二叉木挿入形式機能がある:a、bを検索し、最大値c、最小値dを求め、前駆eを求め、後継fを求め、削除点gを求める.合併splayツリー(ここでの削除は直接splayツリーの結点下標を利用する)(2)区間形式(挿入は区間形式で挿入される)区間形式の伸張ツリーは線分ツリーに相当し、線分ツリーのすべての操作をサポートするとともに、操作区間[a,b]のような区間挿入をサポートし、根をa-1、根の右子をb+1とし、では、根の右の子の左の子が求めている区間のある点を区間に挿入するのも一つの道理で注意しなければならないのは、ここでinit()が自動的に左右の区間を生成し、その後の操作を便利にすることである.実際に有効な区間範囲に注意すればよい.(区間削除またはその他の操作は,元のシーケンスの下付き文字を利用し,関数により対応するsplayノードの下付き文字を見つけ,区間に変換し,区間を削除する)
この問題は主に二叉木の挿入形式で、挿入前駆を探して後継削除点を探して合併する必要がある.このいくつかの機能削除点は、削除する必要がある点splayをルートにし、すべての連絡(左右のノードの父親のノードを0に設定する)を取り除き、左右のサブツリーを合併すればよい.次にrootを新しくマージしたツリーのルートに設定してマージするには、左サブツリーの最大キー値ノードをルートに、右サブツリーを左サブツリーのルートに挿入します.左のサブ数がない場合、マージの結果は直接右のサブツリーになります.
現在の木が動物であるか、人間がsplayの木で完成できるかをマークします.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
using namespace std;
#define exp 1e-8
#define INF 0x3f3f3f3f
#define ll long long
#define set(a,b) memset(a,b,sizeof(a));
#define set(a,b) memset(a,b,sizeof(a));
#define for1(a,b) for(int a=1;a<=b;a++)//1---(b)
#define for0(a,b) for(int a=0;a<=b;a++)//0---(b)
void bug(string st="bug")
{cout<template<typename __ll>
inline void READ(__ll &m){
    __ll x=0,f=1;char ch=getchar();
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    m=x*f;
}
template<typename __ll>
inline void read(__ll &m){READ(m);}
template<typename __ll>
inline void read(__ll &m,__ll &a){READ(m);READ(a);}
template<typename __ll>
inline void read(__ll &m,__ll &a,__ll &b){READ(m);READ(a);READ(b);}
const int MAXN=100000+1000;
#define dat int
#define Key_value ch[ch[root][1]][0]
struct splaytree
{
    int ch[MAXN][2];  //  
    int pre[MAXN];   //  
    dat key[MAXN];  //  
    int size[MAXN];  //  
    int root,tot1;  //       
    int s[MAXN],tot2;  //      ，        ，        
    int kind,ans;
    void addnode(int &r,int father,dat k)
    {
        if(tot2) r=s[tot2--];
        else r=++tot1;
        ch[r][0]=ch[r][1]=0;
        pre[r]=father;
        key[r]=k;
        size[r]=1;
    }
    void push_up(int r)
    {
        if(!r)return ;  //    ，   0       
       int lson=ch[r][0],rson=ch[r][1];
       size[r]=1+size[lson]+size[rson];
    }
    void init()
    {
        kind=-1,ans=0;
        root=tot1=tot2=0;
        ch[0][0]=ch[0][1]=pre[0]=size[0]=0;
        key[0]=-INF;
    }
    void rotate(int x,int kind)
    {
        int y=pre[x];
        int z=pre[y];
        ch[y][!kind]=ch[x][kind];
        pre[ch[x][kind]]=y;
        if(z)   ch[z][ch[z][1]==y] = x;
        pre[x]=pre[y];
        ch[x][kind]=y;
        pre[y]=x;
        push_up(y);
    }
    void splay(int r,int goal)  //r splay     
    {
        while(pre[r]!=goal)    //  push_down   rotate   
        {
            if(pre[pre[r]]==goal)
            {
                rotate(r,ch[pre[r]][0]==r);
                continue;
            }
            int y=pre[r];
            int z=pre[y];
            int kind=  ch[z][0]==y;
            if(ch[y][kind]==r)
                rotate(r,!kind),rotate(r,kind);
            else rotate(y,kind),rotate(r,kind);
        }
        push_up(r);
        if(goal==0)  root=r;
    }
    int insert(int &x,int f,int val)  //         
    {
        if(x==0)
        {
            addnode(x,f,val);
            int tmp=x;
            splay(tmp,0);
            return tmp;  //          ，
        }                //   int &x，splay  ch[pre[x]]][]  ，  x    
        if(val==key[x])
            return x;
        if(valreturn insert(ch[x][0],x,val);
        else
            return insert(ch[x][1],x,val);
    }
    void erase(int r)    //         
    {
        if(!r)return ;
        s[++tot2]=r;
    }
    int get_next()    //         
    {
        int r=root;
        r=ch[r][1];  //         
        while(ch[r][0])
            r=ch[r][0];
        return r;
    }
    int get_pre()  //         
    {
        int r=root;
        r=ch[r][0];
        while(ch[r][1])
            r=ch[r][1];
        return r;
    }
    int get_max(int r)   //              
    {
        while(ch[r][1])
            r=ch[r][1];
        return r;
    }
    void Union(int lroot,int rroot)  //     
    {
        if(lroot==0)  //     ，root       
        {
            root=rroot;
            return ;
        }
        int r=get_max(lroot); //                
        splay(r,0);   //      
        ch[root][1]=rroot;  //  
        pre[rroot]=root;
        push_up(root);
    }
    void cut_root(int idx)  //       ，
    {
        splay(idx,0);
        int r=root;
        int lroot=ch[r][0];
        int rroot=ch[r][1];
        pre[lroot]=pre[rroot]=0;  //    
        erase(r);
        Union(lroot,rroot);
    }
    int find(int val,int r)  //  ，          
    {
        if(!r) return 0;
        if(val==key[r])
            return r;
        if(valreturn find(val,ch[r][0]);
        return find(val,ch[r][1]);
    }
    void solve(int val)
    {
        int r=find(val,root);
        if(!r)  //            
        {
            r=insert(root,0,val);
            splay(r,0);
            int preidx=get_pre();
            int nextidx=get_next();
            if((preidx!=0&&nextidx==0)||(preidx!=0&&nextidx!=0&&abs(key[preidx]-key[r])<=abs(key[nextidx]-key[r])))
            {
                ans+=abs(key[preidx]-key[r]);
                cut_root(preidx);
            }
            else
            {
                ans+=abs(key[nextidx]-key[r]);
                cut_root(nextidx);
            }
            push_up(root);
        }
        ans%=1000000;
        cut_root(r);
        push_up(root);
        if(size[root]==0)
            kind=-1;
    }
}t;
int main()
{

    int n,a,b,ans;
    read(n);
    t.init();
    while(n--)
    {
        read(a,b);
        if(t.kind==-1||t.kind==a)
            t.insert(t.root,0,b),t.kind=a;
        else
            t.solve(b);
    }
    printf("%d
",t.ans);
    return 0;
}