P2596 [ZJOI2006]书架

admin

剩下的这个插入我做了一个多小时，思路其实很简单，T==0的话不做任何操作，T==1的话把它和他的后继进行交换，T==-1的话和前驱进行交换。我在写的时候

1. swap(a[x].val,a[q[S]].val);
   
2. swap(q[a[x].val],q[S]);

复制代码

没有意识到错误，调了很长的时间。最后用了直观的方法，

1.      cin>>S>>T;
   
2.               int x;
   
3.               if (T!=0)
   
4.                     {
   
5.                            if (T==-1)x=Pre(q[S]);
   
6.                            if (T== 1)x=Suc(q[S]);
   
7.                                     
   
8.                            ///这两个交换我曾经搞糊涂了
   
9.                            int v=a[x].val;
   
10.                            swap(a[x].val,a[q[S]].val);
    
11.                            swap(q[v],q[S]);
    
12.                      }

复制代码

admin

最后奉上我的程序，前前后后3个多小时，丢人

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int inf=99999999;
   
4. const int N=80100;
   
5. struct node
   
6. {
   
7.         int val,fa,s[2],sz;  ///s0s1左右儿子
   
8. } a[N];
   
9. int p[N],q[N],n,m, tot, root;
   
10. void ArrayPr()   /// 调试监视使用
    
11. {
    
12.         cout<<endl<<"  i ";
    
13.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
14.         cout<<endl<<"val ";
    
15.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
16.         cout<<endl<<" s0 ";
    
17.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
    
18.         cout<<endl<<" s1 ";
    
19.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
    
20.         cout<<endl<<" sz ";
    
21.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
    
22.         cout<<endl<<" fa ";
    
23.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
    
24.         cout<<endl;
    
25. }
    
26. void BSTPr(int rt)   
    
27. {
    
28.         if (a[rt].s[0]>0)  BSTPr(a[rt].s[0]);
    
29.         cout<<a[rt].val<<' ';
    
30.         if (a[rt].s[1]>0)  BSTPr(a[rt].s[1]);
    
31. }
    
32. void pushup(int rt)  
    
33. {
    
34.         int l=a[rt].s[0], r=a[rt].s[1];
    
35.         a[rt].sz=a[l].sz+a[r].sz+1;
    
36. }
    
37. int Son(int x)
    
38. {
    
39.         int y=a[x].fa;
    
40.         return  a[y].s[1]==x;
    
41. }
    
42. void R(int x)
    
43. {
    
44.         int y=a[x].fa;
    
45.         int z=a[y].fa;
    
46.         int k=Son(x);
    
47.         int v=a[x].s[k^1];
    
48.         a[y].s[k]=v,a[v].fa=y;
    
49.         a[z].s[Son(y)]=x,a[x].fa=z;
    
50.         a[x].s[k^1]=y,a[y].fa=x;
    
51.         pushup(y),pushup(x);
    
52. }
    
53. void Splay(int x,int rt=root)
    
54. {
    
55.         rt=a[rt].fa;
    
56.         int y,z;
    
57.         while(a[x].fa!=rt)
    
58.                 {
    
59.                         y=a[x].fa,z=a[y].fa;
    
60.                         if(z!=rt)
    
61.                                 if(Son(x)==Son(y))R(y);
    
62.                                 else R(x);
    
63.                         R(x);
    
64.                 }
    
65.         if(rt==0)root=x;
    
66. }
    
67. 
    
68. int Ask(int S)
    
69. {
    
70.         Splay(S,root);
    
71.         int l=a[root].s[0];
    
72.         return a[l].sz;
    
73. }
    
74. 
    
75. int Query(int rt, int S) ///在RT子树中找第S小
    
76. {
    
77.         int l=a[a[rt].s[0]].sz;  /// RT的左儿子下的个数
    
78.         if(l+1==S) return a[rt].val;
    
79.         if(l+1>S) return Query(a[rt].s[0], S); ///左儿子里去找
    
80.         if(l+1<S) return Query(a[rt].s[1], S-(l+1));
    
81. }
    
82. void Top(int S)
    
83. {
    
84.         Splay(S,root);
    
85.         int  x=root;
    
86.         int l=a[x].s[0];
    
87.         int r=a[x].s[1];///右儿子
    
88.         if (r==0) a[x].s[1]=l;
    
89.         else
    
90.                 {
    
91. 
    
92.                         int p=r;
    
93.                         ///找最左节点
    
94.                         while (a[p].s[0]>0) p=a[p].s[0];
    
95.                         Splay(p,r);
    
96.                         a[p].s[0]=l;
    
97.                         a[l].fa=p;
    
98.                         pushup(p);
    
99.                 }
    
100.         a[x].s[0]=0;
     
101. }
     
102. void Bottom(int S)
     
103. {
     
104.         Splay(S,root);
     
105.         int x=root;
     
106.         int l=a[x].s[0];
     
107.         int r=a[x].s[1];
     
108.         if (l==0) a[x].s[0]=r;
     
109.         else
     
110.                 {
     
111.                         int p=l;
     
112.                         while (a[p].s[1]>0) p=a[p].s[1];
     
113.                         Splay(p,r);
     
114. 
     
115.                         a[p].s[1]=r;
     
116.                         a[r].fa=p;
     
117.                         pushup(p);
     
118.                 }
     
119.         a[x].s[1]=0;
     
120. }
     
121. 
     
122. int Pre(int S)
     
123. {
     
124.         Splay(S,root);
     
125.         int l=a[S].s[0], ans=0;
     
126.         if (l==0) return 0;
     
127.         int p=l;
     
128.         while(a[p].s[1]>0) p=a[p].s[1];
     
129.         return p;
     
130. }
     
131. int Suc(int S)
     
132. {
     
133.                 Splay(S,root);
     
134.         int r=a[S].s[1];
     
135.         if (r==0) return 0;
     
136.         int p=r;
     
137.         while(a[p].s[0]>0) p=a[p].s[0];
     
138.         return p;
     
139. }
     
140. int Build(int l,int r) ///前n个数直接建个满二叉树
     
141. {
     
142.         if (l>r) return 0;
     
143.         if (l==r)
     
144.                 {
     
145.                         a[l].val=p[l];
     
146.                         a[l].s[0]=a[l].s[1]=0;
     
147.                         a[l].sz=1;
     
148.                         return l;
     
149.                 }
     
150.         int m=(l+r)/2;
     
151.         a[m].val=p[m];
     
152.         int L=a[m].s[0]=Build(l,m-1);
     
153.         int R=a[m].s[1]=Build(m+1,r);
     
154.         a[L].fa=a[R].fa=m;
     
155.         a[m].sz=a[L].sz+a[R].sz+1;
     
156.         return m;
     
157. }
     
158. int main()
     
159. {
     
160.         cin>>n>>m;
     
161.         for (int x,i=1; i<=n; i++)
     
162.                 {
     
163.                         cin>>x;
     
164.                         p[i]=x;
     
165.                         q[x]=i;
     
166.                 }
     
167.         tot=n;
     
168.         root=Build(1,n);
     
169.         for (int i=1; i<=n; i++)cout<<q[i]<<' ';
     
170.         cout<<endl;
     
171. 
     
172.         ///初始建树完毕
     
173.         string opt;
     
174.         int S,T;
     
175.         while(m--)
     
176.                 {
     
177.                         cin>>opt;
     
178.                         if(opt=="Top")
     
179.                                 {
     
180.                                         cin>>S;
     
181.                                         Top(q[S]);
     
182.                                 }
     
183.                         if(opt=="Bottom")
     
184.                                 {
     
185.                                         cin>>S;
     
186.                                         Bottom(q[S]);
     
187.                                 }
     
188.                         if(opt=="Insert")
     
189.                                 {
     
190.                                         cin>>S>>T;
     
191.                                         int x;
     
192.                                         if (T==-1)x=Pre(q[S]);
     
193.                                         if (T== 1)x=Suc(q[S]);
     
194.                                         ///这两个交换我曾经搞糊涂了
     
195.                                         swap(q[a[x].val],q[S]);
     
196.                                         swap(a[x].val,a[q[S]].val);
     
197.                                 }
     
198.                         if(opt=="Ask")
     
199.                                 {
     
200.                                         cin>>S;
     
201.                                         cout<<Ask(q[S])<<endl;
     
202.                                 }
     
203.                         if(opt=="Query")
     
204.                                 {
     
205.                                         cin>>S;
     
206.                                         cout<<Query(root,S)<<endl;
     
207.                                 }
     
208.                 }
     
209. 
     
210.         return 0;
     
211. }
     
212. /*
     
213. 10 10
     
214. 1 3 2 7 5 8 10 4 9 6
     
215. Query 3
     
216. Top 5
     
217. Ask 6
     
218. Bottom 3
     
219. Ask 3
     
220. Top 6
     
221. Insert 4 -1
     
222. Query 5
     
223. Query 2
     
224. Ask 2
     
225. */
     

复制代码