#文藝平衡樹

金牌導航 Splay-2

題目大意

給你一個1~n的序列，然后對序列的區間做若干次翻轉，問你最后的序列

輸入樣例

5 3 1 3 1 3 1 4

輸出樣例

4 3 2 1 5

數據范圍

$1?n,m?10^5,1?l?r?n$

解題思路

對于該序列，可以用Splay來存儲（直接存數字）
對于翻轉區間，在中序遍歷中，原順序是左中右，翻轉后為右中左，相當于把區間內所有節點的左右子樹交換，這里可以用標記記下，當用到時再下傳（形如線段樹的lazy）
對于選取的區間，可以將序列旋轉成如下狀態，此時就可以直接得到所選區間的子樹

最后直接按順序輸出即可

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 100010 #define MAXN 200000 using namespace std; int n, m, x, y, w, rt, a[N], s[N], p[N], ls[N], rs[N], sz[N], fa[N]; int ss(int x) {return x == ls[fa[x]]; } void down(int x)//標記下傳 {if (x && p[x]){p[ls[x]] ^= 1;p[rs[x]] ^= 1;swap(ls[x], rs[x]);p[x] = 0;} } void up(int x)//計算節點個數 {sz[x] = sz[ls[x]] + sz[rs[x]] + 1; } void take_up(int x)//向上移動 {int y = fa[x], z = fa[y];down(y);down(x);int g = ss(x)? rs[x]: ls[x];if (z) ss(y)? ls[z] = x: rs[z] = x;if (ss(x)) rs[x] = y, ls[y] = g;else ls[x] = y, rs[y] = g;if (g) fa[g] = y;fa[y] = x;fa[x] = z;up(y);up(x); } void Splay(int x, int y) {while(fa[x] != y){if (fa[fa[x]] != y)ss(x) == ss(fa[x])? take_up(fa[x]): take_up(x);take_up(x);}if (!y) rt = x; } int find(int v)//查找目標節點 {int x = rt;while(x){down(x);if (v <= sz[ls[x]]) x = ls[x];else{v -= sz[ls[x]] + 1;if (!v) return x;x = rs[x];}} } int build(int lst, int l, int r)//建樹 {if (l > r) return 0;int x = ++w, mid = (l + r) >> 1;s[x] = a[mid];p[x] = 0;fa[x] = lst;ls[x] = build(x, l, mid - 1);rs[x] = build(x, mid + 1, r);up(x);return x; } void write(int x) {down(x);if (ls[x]) write(ls[x]);//按中序遍歷if (s[x] != -MAXN && s[x] != MAXN)printf("%d ", s[x]);if (rs[x]) write(rs[x]); } int main() {scanf("%d%d", &n, &m);a[1] = -MAXN;a[n + 2] = MAXN;for (int i = 2; i <= n + 1; ++i)a[i] = i - 1;rt = build(0, 1, n + 2);while(m--){scanf("%d%d", &x, &y);x = find(x);y = find(y + 2);Splay(x, 0);Splay(y, x);p[ls[rs[rt]]] ^= 1;}write(rt);return 0; }

總結

以上是生活随笔為你收集整理的【Splay】文艺平衡树（金牌导航 Splay-2）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。