首页 > 代码库 > Splay!

Splay!

  1 #include<cstdio>    2 #include<cstdlib>    3 const int mod =1000000007;    4 const int inf  = ~0u>>2;    5 const int maxn = 200010;    6 int lim;    7 struct SplayTree {    8 19.    int sz[maxn];    9 20.    int ch[maxn][2];   10 21.    int pre[maxn];   11 22.    int rt,top;   12 23.    inline void up(int x){   13 24.        sz[x]  = cnt[x]  + sz[ ch[x][0] ] + sz[ ch[x][1] ];   14 25.    }   15 26.    inline void Rotate(int x,int f){   16 27.        int y=pre[x];   17 28.        ch[y][!f] = ch[x][f];   18 29.        pre[ ch[x][f] ] = y;   19 30.        pre[x] = pre[y];   20 31.        if(pre[x]) ch[ pre[y] ][ ch[pre[y]][1] == y ] =x;   21 32.        ch[x][f] = y;   22 33.        pre[y] = x;   23 34.        up(y);   24 35.    }   25 36.    inline void Splay(int x,int goal){//将x旋转到goal的下面   26 37.        while(pre[x] != goal){   27 38.            if(pre[pre[x]] == goal) Rotate(x , ch[pre[x]][0] == x);   28 39.            else   {   29 40.                int y=pre[x],z=pre[y];   30 41.                int f = (ch[z][0]==y);   31 42.                if(ch[y][f] == x) Rotate(x,!f),Rotate(x,f);   32 43.                else Rotate(y,f),Rotate(x,f);   33 44.            }   34 45.        }   35 46.        up(x);   36 47.        if(goal==0) rt=x;   37 48.    }   38 49.    inline void RTO(int k,int goal){//将第k位数旋转到goal的下面   39 50.        int x=rt;   40 51.        while(sz[ ch[x][0] ] != k-1) {   41 52.            if(k < sz[ ch[x][0] ]+1) x=ch[x][0];   42 53.            else {   43 54.                k-=(sz[ ch[x][0] ]+1);   44 55.                x = ch[x][1];   45 56.            }   46 57.        }   47 58.        Splay(x,goal);   48 59.    }   49 60.    inline void vist(int x){   50 61.        if(x){   51 62.            printf("结点%2d : 左儿子  %2d   右儿子  %2d   %2d sz=%d\n",x,ch[x][0],ch[x][1],val[x],sz[x]);   52 63.            vist(ch[x][0]);   53 64.            vist(ch[x][1]);   54 65.        }   55 66.    }   56 67.    inline void Newnode(int &x,int c){   57 68.        x=++top;   58 69.        ch[x][0] = ch[x][1] = pre[x] = 0;   59 70.        sz[x]=1; cnt[x]=1;   60 71.        val[x] = c;   61 72.    }   62 73.    inline void init(){   63 74.        ans=0;type=-1;   64 75.        ch[0][0]=ch[0][1]=pre[0]=sz[0]=0;   65 76.        rt=top=0; cnt[0]=0;   66 77.        Newnode(rt,-inf);   67 78.        Newnode(ch[rt][1],inf);   68 79.        pre[top]=rt;   69 80.        sz[rt]=2;   70 81.    }   71 82.    inline void Insert(int &x,int key,int f){   72 83.        if(!x) {   73 84.            Newnode(x,key);   74 85.            pre[x]=f;   75 86.            Splay(x,0);   76 87.            return ;   77 88.        }   78 89.        if(key==val[x]){   79 90.            cnt[x]++;   80 91.            sz[x]++;   81 92.            return ;   82 93.        }else if(key<val[x]) {   83 94.            Insert(ch[x][0],key,x);   84 95.        } else {   85 96.            Insert(ch[x][1],key,x);   86 97.        }   87 98.        up(x);   88 99.    }   89 100.    void Del(){   90 101.         int t=rt;   91 102.         if(ch[rt][1]) {   92 103.             rt=ch[rt][1];   93 104.             RTO(1,0);   94 105.             ch[rt][0]=ch[t][0];   95 106.             if(ch[rt][0]) pre[ch[rt][0]]=rt;   96 107.         }   97 108.         else rt=ch[rt][0];   98 109.         pre[rt]=0;   99 110.         up(rt);  100 111.    }  101 112.    void findpre(int x,int key,int &ans){  102 113.        if(!x)  return ;  103 114.        if(val[x] <= key){  104 115.            ans=x;  105 116.            findpre(ch[x][1],key,ans);  106 117.        } else  107 118.            findpre(ch[x][0],key,ans);  108 119.    }  109 120.    void findsucc(int x,int key,int &ans){  110 121.        if(!x) return ;  111 122.        if(val[x]>=key) {  112 123.            ans=x;  113 124.            findsucc(ch[x][0],key,ans);  114 125.        } else  115 126.            findsucc(ch[x][1],key,ans);  116 127.    }  117 128.    void solve() {  118 129.        int a,b,x,y;  119 130.        scanf("%d%d",&a,&b);  120 131.        if(a==type || sz[rt]==2){  121 132.               122 133.            Insert(rt,b,0),type=a;  123 134.            //printf("type=%d\n",type);  124 135.        }  125 136.        else {  126 137.            findpre(rt,b,x);  127 138.            findsucc(rt,b,y);  128 139.            if(abs(val[x]-b) <= abs(val[y]-b)) {  129 140.                ans+=abs(val[x]-b);  130 141.                ans%=mod;  131 142.                Splay(x,0);  132 143.                Del();  133 144.            }  134 145.            else {  135 146.                ans+=abs(val[y]-b);  136 147.                ans%=mod;  137 148.                Splay(y,0);  138 149.                Del();  139 150.            }  140 151.        }  141 152.        //spt.vist(rt);  142 153.    }  143 154.    int cnt[maxn];  144 155.    int val[maxn];  145 156.    int type;  146 157.    int ans;  147 158.}spt;  148 159.int main()  149 160.{  150 161.    int n;  151 162.    scanf("%d",&n);  152 163.    spt.init();  153 164.    while(n--)  spt.solve();  154 165.    printf("%d\n",spt.ans);  155 166.    return 0;  156 }  
View Code