http://codevs.cn/problem/1514/

題解：

Splay，因?yàn)闆](méi)辦法根據(jù)給出的書(shū)的編號(hào)確定書(shū)的位置，也就沒(méi)辦法做到log(n)的查詢(xún)，所以采用自底向上的伸展方式，那么就需要用pa數(shù)組記錄節(jié)點(diǎn)的上個(gè)結(jié)點(diǎn)。

算法實(shí)現(xiàn)上建立了兩個(gè)虛擬節(jié)點(diǎn)來(lái)避免溢出——據(jù)HZWER。

加了很多注解。

體會(huì)了一下，因?yàn)閙ove操作的統(tǒng)一性，所以加上兩個(gè)虛擬節(jié)點(diǎn)后有利于繼續(xù)維護(hù)插入操作的統(tǒng)一性。否則除非給移動(dòng)到頂和底層的另寫(xiě)函數(shù)，沒(méi)辦法用一個(gè)move函數(shù)解決了否則溢出，因?yàn)榭展?jié)點(diǎn)不能作為根節(jié)點(diǎn)。

寫(xiě)了蚱蜢以后才逐漸理解。

第一個(gè)用的HZWER的splay，第二個(gè)是我寫(xiě)的。

代碼：

版本1： 總時(shí)間耗費(fèi): 1637ms?
總內(nèi)存耗費(fèi): 2 kB

#include<cstdio> #include<cstring> using namespace std;const int INF = 1e9 + 7; const int maxn = 80000 + 10;int n, m, root; int ch[maxn][2], p[maxn], a[maxn], s[maxn], v[maxn], id[maxn];void update(int k) {s[k] = s[ch[k][0]] + s[ch[k][1]] + 1; }void rotate(int x, int &k) {int y = p[x], z = p[y];int d = ch[y][0] == x ? 0 : 1; int d2 = ch[z][0] == y ? 0 : 1; if(y == k) k = x; else ch[z][d2] = x;p[x] = z; p[y] = x; p[ch[x][d^1]] = y; ch[y][d] = ch[x][d^1]; ch[x][d^1] = y; update(y); update(x); }//自底向上的伸展 void splay(int x, int &k) {while(x != k) {int y = p[x], z = p[y]; if(y != k) { if(ch[y][0] == x ^ ch[z][0] == y) rotate(x, k); else rotate(y, k); }rotate(x, k); } }//類(lèi)似線段樹(shù)的build void build(int l, int r, int pa) {if(l > r) return; if(l == r) {v[l] = a[l]; s[l] = 1; p[l] = pa; if(l < pa) ch[pa][0] = l; else ch[pa][1] = l; return; }int mid = (l+r) >> 1; build(l, mid-1, mid); build(mid+1, r, mid); v[mid] = a[mid]; p[mid] = pa; update(mid); if(mid < pa) ch[pa][0] = mid; else ch[pa][1] = mid; }//在這個(gè)樹(shù)中查詢(xún)第rank個(gè) int find(int k, int rank) {int l = ch[k][0], r = ch[k][1]; if(s[l]+1 == rank) return k; else if(s[l] >= rank) return find(l, rank); else return find(r, rank-s[l]-1); }//刪除排在第k位的 void remove(int k) {int x, y, z; x = find(root, k-1); y = find(root, k+1); splay(x, root); splay(y, ch[x][1]); z = ch[y][0]; ch[y][0] = 0; p[z] = s[z] = 0; update(y); update(x); }void move(int k, int val) {int o = id[k], x, y, rank;splay(o, root); rank = s[ch[o][0]] + 1; remove(rank); //x是要插入的位置的上一個(gè)點(diǎn)，y是要插入的位置 //最后插入到y(tǒng)的左兒子也就是取代了y原來(lái)的位置 if(val == INF) x = find(root, n), y = find(root, n+1); //插入到底部 此時(shí)共n+1個(gè)點(diǎn) 成為第n+1個(gè)點(diǎn)else if(val == -INF) x = find(root, 1), y = find(root, 2); //插入到頂部 成為第2個(gè)點(diǎn)else x = find(root, rank+val-1), y = find(root, rank+val); //插入到中間 成為第rank+val個(gè)點(diǎn)（rank的值是原來(lái)的排名+1） splay(x, root); splay(y, ch[x][1]); s[o] = 1; p[o] = y; ch[y][0] = o; update(y); update(x); }int main() {scanf("%d%d", &n, &m);//加入1和n+2兩個(gè)虛擬結(jié)點(diǎn)，避免溢出 for(int i = 2; i <= n+1; i++) scanf("%d", &a[i]), id[a[i]] = i; build(1, n+2, 0); root = (n+3) >> 1; char cmd[10]; int S, T; for(int i = 1; i <= m; i++) {scanf("%s%d", cmd, &S); //避免了標(biāo)準(zhǔn)函數(shù)讀char讀到回車(chē)什么奇怪的東西switch(cmd[0]) {case 'T': move(S, -INF); break; case 'B': move(S, INF); break; case 'I': scanf("%d", &T); move(S, T); break; case 'A': splay(id[S], root); printf("%d\n", s[ch[id[S]][0]]-1); break; case 'Q': printf("%d\n", v[find(root, S+1)]); break; }}return 0; }

版本2：

總時(shí)間耗費(fèi): 1067ms?
總內(nèi)存耗費(fèi): 3 MB

#include<cstdio> #include<cstring> using namespace std;const int INF = 1e9 + 7; const int maxn = 80000 + 10;int n, m, root; int ch[maxn][2], p[maxn], a[maxn], s[maxn], v[maxn], id[maxn];void update(int k) {s[k] = s[ch[k][0]] + s[ch[k][1]] + 1; }void rotate(int& px, int& x, int d) {int t = ch[x][d]; ch[x][d] = px; ch[px][d^1] = t; p[x] = p[px]; p[px] = x; p[t] = px; update(px); update(x); px = x; }void splay(int x, int& k) {while(x != k) {int y = p[x], z = p[y];int d = ch[y][0] == x ? 0 : 1;int d2 = ch[z][0] == y ? 0 : 1;if(y != k) rotate(ch[z][d2], x, d^1); else rotate(k, x, d^1);} }void build(int L, int R, int P, int d) {if(L == R) { s[L] = 1; p[L] = P; ch[P][d] = L; return; }int M = (L+R) >> 1;p[M] = P; ch[P][d] = M;if(M-1 >= L) build(L, M-1, M, 0); if(R >= M+1) build(M+1, R, M, 1);update(M); }int find(int k, int rank) {int l = ch[k][0], r = ch[k][1]; if(s[l]+1 == rank) return k; else if(s[l] >= rank) return find(l, rank); else return find(r, rank-s[l]-1); }void remove(int k) {int x, y, z; x = find(root, k-1); y = find(root, k+1); splay(x, root); splay(y, ch[x][1]); z = ch[y][0]; ch[y][0] = 0; p[z] = s[z] = 0; update(y); update(x); }void move(int k, int val) {int o = id[k], x, y, rank;splay(o, root); rank = s[ch[o][0]] + 1; remove(rank); if(val == INF) x = find(root, n), y = find(root, n+1); else if(val == -INF) x = find(root, 1), y = find(root, 2); else x = find(root, rank+val-1), y = find(root, rank+val); splay(x, root); splay(y, ch[x][1]); s[o] = 1; p[o] = y; ch[y][0] = o; update(y); update(x); }int main() {scanf("%d%d", &n, &m);for(int i = 2; i <= n+1; i++) scanf("%d", &v[i]), id[v[i]] = i; build(1, n+2, 0, 1); root = (n+3) >> 1; char cmd[10]; int S, T; for(int i = 1; i <= m; i++) {scanf("%s%d", cmd, &S); switch(cmd[0]) {case 'T': move(S, -INF); break; case 'B': move(S, INF); break; case 'I': scanf("%d", &T); move(S, T); break; case 'A': splay(id[S], root); printf("%d\n", s[ch[id[S]][0]]-1); break; case 'Q': printf("%d\n", v[find(root, S+1)]); break; }}return 0; }

總結(jié)

以上是生活随笔為你收集整理的[codevs 1514] 书架的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。