維護(hù)書架

金牌導(dǎo)航 無旋式treap-1

題目大意

給出一個(gè)序列a，編號(hào)為1~n，讓你做若干操作，操作有五種：
1.把第x個(gè)數(shù)放在最前面
2.把第x個(gè)數(shù)放在最后面
3.把第x個(gè)數(shù)和第$x\pm 1$個(gè)數(shù)交換
4.查詢編號(hào)為i的數(shù)前面有多少個(gè)數(shù)
5.查詢第i個(gè)數(shù)的編號(hào)

輸入樣例

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

數(shù)據(jù)范圍

$3?n,m?8\times 10^4,1?a_i?n$

解題思路

用無旋式treap維護(hù)該數(shù)列
前三項(xiàng)就先把數(shù)字拆出來，然后再按要求放回去
對(duì)于操作四，在建點(diǎn)的時(shí)候寄一個(gè)標(biāo)記，記下編號(hào)為x的數(shù)在樹中的編號(hào)，然后搜一下就行了
對(duì)于操作五，就直接搜就行了（代碼里是把書拆開，因?yàn)榭梢允∪ゴ蛞粋€(gè)函數(shù)）

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define sto_wyc_orz 666666 #define N 80080 using namespace std; int n, m, x, y, w, t1, t2, t3, t4, rt, v[N], s[N], fa[N], ls[N], rs[N], pri[N], size[N]; string str; void up(int x) {size[x] = size[ls[x]] + size[rs[x]] + 1;return; } int newnode(int x)//建點(diǎn) {s[++w] = x;pri[w] = rand();size[w] = 1;v[x] = w;return w; } int merge(int x, int y)//合并 {if (!x || !y) return x + y;if (pri[x] < pri[y]){rs[x] = merge(rs[x], y);fa[rs[x]] = x;up(x);return x;}else{ls[y] = merge(x, ls[y]);fa[ls[y]] = y;up(y);return y;} } void split(int x, int k, int &a, int &b, int faa, int fab)//拆分 {if (!x){a = b = 0;return;}if (k <= size[ls[x]]){fa[x] = fab;b = x;split(ls[x], k, a, ls[x], faa, x);}else{fa[x] = faa;a = x;split(rs[x], k - size[ls[x]] - 1, rs[x], b, x, fab);}up(x); } void insert(int x, int y) {split(rt, x, t1, t2, 0, 0);rt = merge(t1, merge(newnode(y), t2)); } int find(int x) {int sum = size[ls[x]] + 1;while(x != rt){if (x == rs[fa[x]]) sum += size[ls[fa[x]]] + 1;x = fa[x];}return sum; } int main() {srand(sto_wyc_orz);scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i){ scanf("%d", &x);insert(i - 1, x);}while(m--){cin>>str;scanf("%d", &x);if (str == "Top"){x = find(v[x]);split(rt, x, t1, t3, 0, 0);split(t1, x - 1, t1, t2, 0, 0);//拆分再按要求合并rt = merge(t2, merge(t1, t3));}if (str == "Bottom"){x = find(v[x]);split(rt, x, t1, t3, 0, 0);split(t1, x - 1, t1, t2, 0, 0);rt = merge(t1, merge(t3, t2));}if (str == "Insert"){scanf("%d", &y);x = find(v[x]);if (y > 0){split(rt, x + 1, t3, t4, 0, 0);split(t3, x, t2, t3, 0, 0);split(t2, x - 1, t1, t2, 0, 0);rt = merge(merge(t1, t3), merge(t2, t4));}else if (y < 0){split(rt, x, t3, t4, 0, 0);split(t3, x - 1, t2, t3, 0, 0);split(t2, x - 2, t1, t2, 0, 0);rt = merge(merge(t1, t3), merge(t2, t4));}}if (str == "Ask"){printf("%d\n", find(v[x]) - 1);}if (str == "Query"){split(rt, x, t1, t2, 0, 0);y = t1;while(rs[y]) y = rs[y];//拆分后找最右邊的，即第x個(gè)printf("%d\n", s[y]);rt = merge(t1, t2);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【FHQ treap】维护书架（金牌导航 无旋式treap-1）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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