Splay！

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