1. long findpre(long x)
2. {
3. long left=leftson[x];
4. while(rightson[left]!=0)left=rightson[left];
5. return left;
6. }

1. long findsuc(long x)
2. {
3. long right=rightson[x];
4. while(leftson[right]!=0)right=leftson[right];
5. return right;
6. }

1. #include<stdio.h>
2. using namespace std;
3. struct node{long father,left,right,data;}tree[100008];
4. long time=0,n,root,sum=0;bool flag;
5. long MINS(long a,long b)
6. {
7. if(a<b)return a;else return b;
8. }
9. long abs(long a)
10. {
11. if(a<0)return -a;else return a;
12. }
13. void rightrotate(long x)
14. {
15. long y=tree[x].father;long z=tree[y].father;
16. tree[y].left=tree[x].right;
17. if(tree[x].right!=-1){tree[tree[x].right].father=y;}
18. tree[x].father=z;
19. if(z!=-1){if(tree[z].left==y)tree[z].left=x;else tree[z].right=x;}
20. tree[x].right=y;tree[y].father=x;
21. }
22. void leftrotate(long x)
23. {
24. long y=tree[x].father;long z=tree[y].father;
25. tree[y].right=tree[x].left;
26. if(tree[x].left!=-1){tree[tree[x].left].father=y;}
27. tree[x].father=z;
28. if(z!=-1){if(tree[z].left==y)tree[z].left=x;else tree[z].right=x;}
29. tree[x].left=y;tree[y].father=x;
30. }
31. void splay(long x)
32. {
33. while(tree[x].father!=-1)
34. {
35. long y=tree[x].father;long z=tree[y].father;
36. if(z==-1){
37. if(tree[y].left==x)rightrotate(x);else leftrotate(x);
38. }
39. else
40. {
41. if(tree[z].left==y&&tree[y].left==x){rightrotate(y);rightrotate(x);}
42. else if(tree[z].left==y&&tree[y].right==x){leftrotate(x);rightrotate(x);}
43. else if(tree[z].right==y&&tree[y].right==x){leftrotate(y);leftrotate(x);}
44. else {rightrotate(x);leftrotate(x);}
45. }}
46. root=x;
47. }
48. long qq(long x)
49. {
50. long y=tree[x].left;if(y==-1)return y;
51. while(tree[y].right!=-1)y=tree[y].right;
52. return y;
53. }
54. long long hj(long x)
55. {
56. long y=tree[x].right;if(y==-1)return y;
57. while(tree[y].left!=-1)y=tree[y].left;
58. return y;
59. }
60. int  BST_insert(long dat,long x)
61. {
62. if(dat==tree[x].data){flag=false;splay(x);return 0;}
63. if(dat<tree[x].data)
64. {
65. if(tree[x].left==-1){tree[x].left=time;tree[time].father=x;tree[time].left=tree[time].right=-1;tree[time].data=dat;}
66. else BST_insert(dat,tree[x].left);
67. }
68. else
69. {
70. if(tree[x].right==-1){tree[x].right=time;tree[time].father=x;tree[time].left=tree[time].right=-1;tree[time].data=dat;}
71. else BST_insert(dat,tree[x].right);
72. }
73. }
74. int insert(long dat)
75. {
76. flag=true;time++;
77. BST_insert(dat,root);
78. if(flag==false) return 0;
79. splay(time);
80. long q=qq(time);long h=hj(time);
81. long min=2000000000;
82. if(q!=-1)min=MINS(min,abs(tree[q].data-dat));
83. if(h!=-1)min=MINS(min,abs(tree[h].data-dat));
84. sum+=min;
85. }
86. int main()
87. {
88. //freopen("test.in","r",stdin);freopen("testWA.out","w",stdout);
89. long n,a1;
90. while(scanf("%d",&n)!=-1){
91. sum=0;time=0;
92. scanf("%ld",&a1);
93. sum=a1;time++;tree[time].father=-1;
94. tree[time].left=tree[time].right=-1;
95. tree[time].data=a1;root=time;
96. for(long i=1;i<=n-1;i++)
97. {
98. long dats=0;scanf("%ld",&dats);insert(dats);
99. }
100. printf("%ld\n",sum);}
101. return 0;
102. }

最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。
1． 被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为a，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为a-b和a+b，那么领养者将会领养特点值为a-b的那只宠物。 2． 收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为a，存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b，那么特点值为a-b的那个领养者将成功领养该宠物。
一个领养者领养了一个特点值为a的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为abs(a-b)。【任务描述】你得到了一年当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。

第一行为一个正整数n，n<=80000，表示一年当中来到收养所的宠物和领养者的总数。接下来的n行，按到来时间的先后顺序描述了一年当中来到收养所的宠物和领养者的情况。每行有两个正整数a, b，其中a=0表示宠物，a=1表示领养者，b表示宠物的特点值或是领养者希望领养宠物的特点值。（同一时间呆在收养所中的，要么全是宠物，要么全是领养者，这些宠物和领养者的个数不会超过10000个）

仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和mod 1000000以后的结果。

5

0 2

0 4

1 3

1 2

1 5

3

(abs(3-2) + abs(2-4)=3，最后一个领养者没有宠物可以领养)

Splay

1. void del(long x)
2. {
3. //整颗树中就X一个节点了，变成了空树
4. splay(x);if(ch[x][0]==-1&&ch[x][1]==-1){root=-1;return;}
5. //没有左子树
6. if(ch[x][0]==-1){root=ch[x][1];fa[ch[x][1]]=-1;return;}
7. //没有右子树
8. if(ch[x][1]==-1){root=ch[x][0];fa[ch[x][0]]=-1;return;}
9. //左右子树俱全
10. long j=ch[x][0];while(ch[j][1]!=-1)j=ch[j][1];fa[ch[x][0]]=-1;splay(j);ch[j][1]=ch[x][1];fa[ch[x][1]]=j;root=j;
11. }

1. #include<stdio.h>
2. #define MAXN 200000
3. using namespace std;
4. long ch[MAXN][2],fa[MAXN],data[MAXN];
5. long root,tot;long long sum=0;long n;
6. void rotate(long x,int kind)//kind=0 is leftrotate.kind=1 is rightrotate
7. {
8. long y=fa[x];long z=fa[y];
9. ch[y][1-kind]=ch[x][kind];if(ch[x][kind]!=-1)fa[ch[x][kind]]=y;
10. fa[x]=z;if(z!=-1)ch[z][ch[z][1]==y]=x;fa[y]=x;ch[x][kind]=y;
11. }
12. void splay(long x)
13. {
14. while(fa[x]!=-1)
15. {
16. long y=fa[x];long z=fa[y];
17. if(z==-1)rotate(x,ch[y][1]!=x);
18. else
19. {
20. if(ch[z][0]==y)
21. {
22. if(ch[y][0]==x){rotate(y,1);rotate(x,1);}else{rotate(x,0);rotate(x,1);}
23. }
24. else
25. {
26. if(ch[y][0]==x){rotate(x,1);rotate(x,0);}else{rotate(y,0);rotate(x,0);}
27. }
28. }}
29. root=x;
30. }
31. void newnode(long da,long fat)
32. {
33. tot++;data[tot]=da;fa[tot]=fat;ch[tot][0]=ch[tot][1]=-1;
34. }
35. void BST_insert(long dat)
36. {
37. if(root==-1){newnode(dat,-1);root=tot;return;}long now=root;
38. while(true)
39. {
40. if(dat>data[now])
41. {
42. if(ch[now][1]==-1){newnode(dat,now);ch[now][1]=tot;return;}
43. else now=ch[now][1];
44. }
45. else
46. {
47. if(ch[now][0]==-1){newnode(dat,now);ch[now][0]=tot;return;}
48. else now=ch[now][0];
49. }
50. }
51. }
52. void del(long x)
53. {
54. //整颗树中就X一个节点了，变成了空树
55. splay(x);if(ch[x][0]==-1&&ch[x][1]==-1){root=-1;return;}
56. //没有左子树
57. if(ch[x][0]==-1){root=ch[x][1];fa[ch[x][1]]=-1;return;}
58. //没有右子树
59. if(ch[x][1]==-1){root=ch[x][0];fa[ch[x][0]]=-1;return;}
60. //左右子树俱全
61. long j=ch[x][0];while(ch[j][1]!=-1)j=ch[j][1];fa[ch[x][0]]=-1;splay(j);ch[j][1]=ch[x][1];fa[ch[x][1]]=j;root=j;
62. }
63. long prenum,pre,suc,sucnum;
64. void find_pre(long dat)
65. {
66. long now=root;pre=-1;prenum=2100000000;
67. while(true)
68. {
69. if(now==-1)return;
70. if(data[now]<dat&&(dat-data[now])<prenum){pre=now;prenum=dat-data[now];}
71. if(data[now]<dat)now=ch[now][1];else now=ch[now][0];
72. }
73. }
74. void find_suc(long dat)
75. {
76. long now=root;suc=-1;sucnum=2100000000;
77. while(true)
78. {
79. if(now==-1)return;
80. if(data[now]>dat&&(data[now]-dat)<sucnum){suc=now;sucnum=data[now]-dat;}
81. if(data[now]<dat)now=ch[now][1];else now=ch[now][0];
82. }
83. }
84. int main()
85. {
86. long first_data,kind;scanf("%ld",&n);scanf("%ld%ld",&kind,&first_data);tot=0;newnode(first_data,-1);root=tot;sum=0;
87. for(long i=2;i<=n;i++)
88. {
89. long k,dat;scanf("%ld%ld",&k,&dat);
90. if(root==-1)
91. {
92. kind=k;newnode(dat,-1);root=tot;}
93. else
94. {
95. if(k==kind){BST_insert(dat);splay(tot);}
96. else
97. {
98. find_pre(dat);find_suc(dat);
99. if(pre!=-1||suc!=-1)
100. {
101. long mins=2100000001;long num=0;
102. if(pre!=-1&&prenum<mins)mins=prenum,num=pre;
103. if(suc!=-1&&sucnum<mins)mins=sucnum,num=suc;
104. sum=(sum+mins)%1000000;del(num);//printf("%ld\n",mins);
105. }
106. }
107. }
108. }
109. printf("%lld",sum);
110. //for(;;);
111. return 0;
112. }

小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。 小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本书上面就只可能有X-1、X或X+1本书。 当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。
久而久之，小T的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：(1)编号为X的书在书柜的什么位置；(2)从上到下第i本书的编号是多少。

第一行有两个数n，m，分别表示书的个数以及命令的条数；第二行为n个正整数：第i个数表示初始时从上至下第i个位置放置的书的编号；第三行到m+2行，每行一条命令。命令有5种形式： 1． Top S——表示把编号为S的书房在最上面。 2． Bottom S——表示把编号为S的书房在最下面。 3． Insert S T——T∈{-1，0，1}，若编号为S的书上面有X本书，则这条命令表示把这本书放回去后它的上面有X+T本书； 4． Ask S——询问编号为S的书的上面目前有多少本书。 5． Query S——询问从上面数起的第S本书的编号。

对于每一条Ask或Query语句你应该输出一行，一个数，代表询问的答案。

10 10

1 3 2 7 5 8 10 4 9 6

Query 3

Top 5

Ask 6

Bottom 3

Ask 3

Top 6

Insert 4 –1

Query 5

Query 2

Ask 2

2

9

9

7

5

3



数据范围

30%的数据，n,m < = 10000

100%的数据，n,m < = 80000

Day2

1. /**************************************************************
2. Problem: 1861
3. User: SKYDEC
4. Language: C++
5. Result: Accepted
6. Time:1604 ms
7. Memory:8608 kb
8. ****************************************************************/
9. #include<stdio.h>
10. #define MAXN 300000
11. using namespace std;
12. long s[MAXN],f[MAXN],ch[MAXN][2],data[MAXN],root,tot,n,m;
13. void updata(long x)
14. {
15. s[x]=1;if(ch[x][0]!=-1)s[x]+=s[ch[x][0]];if(ch[x][1]!=-1)s[x]+=s[ch[x][1]];
16. }
17. void rot(long x,int kind)
18. {
19. long y=f[x];long z=f[y];
20. ch[y][!kind]=ch[x][kind];if(ch[x][kind]!=-1)f[ch[x][kind]]=y;
21. f[x]=z;if(z!=-1)ch[z][ch[z][1]==y]=x;
22. f[y]=x;ch[x][kind]=y;updata(y);updata(x);
23. }
24. void splay(long x,long place)
25. {
26. while(f[x]!=place)
27. {
28. long y=f[x];long z=f[y];
29. if(z==-1||z==place)rot(x,ch[y][1]!=x);
30. else
31. {
32. if(ch[y][1]==x&&ch[z][1]==y)rot(y,0),rot(x,0);
33. else    if(ch[y][1]==x&&ch[z][0]==y)rot(x,0),rot(x,1);
34. else    if(ch[y][0]==x&&ch[z][0]==y)rot(y,1),rot(x,1);
35. else    rot(x,1),rot(x,0);
36. }
37. }
38. if(place==-1)root=x;
39. }
40. void newnode(long fa,long dat){tot++;f[tot]=fa;s[tot]=1;ch[tot][0]=ch[tot][1]=-1;data[tot]=dat;}
41. long getsize(long x){if(x==-1)return 0;else return s[x];}
42. void insert(long x,long dat,long k)
43. {
44. if(k==1&&ch[x][0]==-1){newnode(x,dat);ch[x][0]=tot;return;}
45. if(k==2+getsize(ch[x][0])&&ch[x][1]==-1){newnode(x,dat);ch[x][1]=tot;return;}
46. if(k<=1+getsize(ch[x][0]))insert(ch[x][0],dat,k);
47. else insert(ch[x][1],dat,k-1-getsize(ch[x][0]));
48. updata(x);
49. }
50. void del(long x)
51. {
52. splay(x,-1);
53. if(ch[x][0]==-1&&ch[x][1]==-1){root=-1;return;}
54. if(ch[x][0]==-1){root=ch[x][1];f[ch[x][1]]=-1;return;}
55. if(ch[x][1]==-1){root=ch[x][0];f[ch[x][0]]=-1;return;}
56. long j=ch[x][0];while(ch[j][1]!=-1)j=ch[j][1];
57. splay(j,x);
58. ch[j][1]=ch[x][1];
59. f[ch[x][1]]=j;f[j]=-1;root=j;
60. updata(j);
61. }
62. long find(long k)
63. {
64. long p=k;
65. long a=root;
66. while(true)
67. {
68. //if(p==5)printf("finding:%ld %ld %ld\n",a,data[a],k);
69. if(k==1+getsize(ch[a][0]))return a;
70. if(k>1+getsize(ch[a][0]))k-=1+getsize(ch[a][0]),a=ch[a][1];
71. else a=ch[a][0];
72. }
73. }
74. long get(long x)
75. {
76. splay(x,-1);
77. return getsize(ch[x][0])+1;
78. }
79. void bltree(long x)
80. {
81. if(x==-1)return;
82. printf("bl:%ld data:%ld l:%ld r:%ld s:%ld\n",x,data[x],ch[x][0],ch[x][1],s[x]);
83. bltree(ch[x][0]);bltree(ch[x][1]);
84. }
85. long pos[100000];long a[100000];
86. int main()
87. {
88. scanf("%ld%ld",&n,&m);for(long i=1;i<=n;i++)scanf("%ld",&a[i]),pos[a[i]]=i;tot=0;root=-1;
89. for(long i=1;i<=n;i++)
90. {
91. if(i==1)newnode(-1,a[i]),root=tot;
92. else{insert(root,a[i],i);if(i%2==0)splay(tot,-1);}
93. }
94. for(long ip=1;ip<=m;ip++)
95. {
96. char p[100];long j,k,i;
97. scanf("%s%ld",&p,&i);
98. if(p[0]=='I')scanf("%ld",&j);
99. if(p[0]=='T'){del(pos[i]);insert(root,i,1);pos[i]=tot;splay(tot,-1);}
100. if(p[0]=='B'){del(pos[i]);insert(root,i,n);pos[i]=tot;splay(tot,-1);}
101. if(p[0]=='I'){long u=get(pos[i]);u=u-1+j;del(pos[i]);insert(root,i,u+1);splay(tot,-1);pos[i]=tot;}
102. if(p[0]=='A'){printf("%ld\n",get(pos[i])-1);}
103. if(p[0]=='Q'){printf("%ld\n",data[find(i)]);}
104. //if(p[0]=='S'){
105. //  for(long i=1;i<=n;i++)printf("%ld ",pos[i]);
106. //  bltree(root);}
107. }
108. //for(;;);
109. return 0;
110. }