# 110 選手班 - 進階資結 ###### tags: `宜中資訊` `CP` Ccucumber12 2021.08.16 --- ## Outline - Lazy Propagation - Sweep Line - Dynamic Segment Tree - 2D Segment Tree - Persistent Segment Tree - Treap --- ## Lazy Propagation ---- ### Problem - 給定數列 $a_1, a_2, a_3, \dots a_N$，請支援以下操作 1. $\text{sum L R}$：計算 $a_L+a_{L+1}+\dots+a_R$ 2. $\text{add L R V}$：將$a_L+a_{L+1}+\dots+a_R$ 加上 $V$ - $N, Q \leq 10^5$ ---- ### Segment Tree - $\text{sum}$：$O(\log N)$ - $\text{add}$：$O((R - L)\log N)$ - Total: $O(QN\log N)$ \:cry: ---- ### KEY - 任意區間皆可在線段樹上表示為 $O(\log N)$ 個區間 - Proof: - 每個區間長度皆為 $2^i$ - 每個長度的區間最多兩個 - 每次操作只更動 $O(\log N)$ 個區間： - 若不須往下遞迴，則將修改的值暫時放在該區間 - 下次需往下遞迴時，再帶著它往下走 ---- ### Lazy Tag ```c= struct node { int val ; // current value int tag ; // value to be pushed down }; ``` ---- - 區間不完整包含： - 將該格 $\text{tag}$ 往下推 ($\text{push}$) - 往下遞迴 - 區間完整包含： - 修改該格的 $\text{val}$ - 暫時將修改的值記錄在 $\text{tag}$ ---- ### Push ```c= void push(int lb, int rb, int idx) { int len = (rb - lb + 1) / 2 ; seg[idx * 2].value += seg[idx].tag * len ; seg[idx*2+1].value += seg[idx].tag * len ; seg[idx * 2].tag += seg[idx].tag ; seg[idx*2+1].tag += seg[idx].tag ; seg[idx].tag = 0 ; } ``` ---- ### Pull ```c= void pull(int idx) { seg[idx].value = seg[idx*2].value + seg[idx*2+1].value ; } ``` ---- ### Lazy Tag - $\text{val}$ 已包含 $\text{tag}$ - $\text{val}$ 未包含 $\text{tag}$ ---- ```c= #include <bits/stdc++.h> using namespace std; struct node { int val ; // current value int tag ; // to be pushed down } ; node seg[1000010] ; void push(int lb, int rb, int idx) { int len = (rb - lb + 1) / 2; seg[idx * 2].val += seg[idx].tag * len ; seg[idx*2+1].val += seg[idx].tag * len ; seg[idx * 2].tag += seg[idx].tag ; seg[idx*2+1].tag += seg[idx].tag ; seg[idx].tag = 0 ; } void pull(int idx) { seg[idx].val = seg[idx*2].val + seg[idx*2+1].val ; } void modify(int l, int r, int v, int lb, int rb, int idx) { if(l <= lb && rb <= r) { seg[idx].val += v * (rb - lb + 1) ; seg[idx].tag += v ; return ; } push(lb, rb, idx) ; int mid = lb + rb >> 1 ; // (lb, mid) (mid+1, rb) if(l <= mid) modify(l, r, v, lb, mid, idx*2) ; if(mid < r) modify(l, r, v, mid+1, rb, idx) ; pull(idx) ; } int query(int l, int r, int lb, int rb, int idx) { if(l <= lb && rb <= r) return seg[idx].val ; push(lb, rb, idx) ; int mid = lb + rb >> 1 ; int ret = 0 ; if(l <= mid) ret += query(l, r, lb, mid, idx*2) ; if(mid < r) ret += query(l, r, mid+1, rb, idx*2+1) ; return ret ; } int main() { int n, q ; // ... } ``` --- ## Sweep Line ---- ### Problem - 給定 $N$ 個二維平面上的矩形，求聯集面積 - $N \leq 10^6$，$0 \leq \text{座標} \leq 10^6$ ----  ---- ### Solution - 假想有一條線由下往上掃 - 每次移動時維護涵蓋到的區間 - 將每個區間長乘上高度加總 ----  ---- 1. 第 $i$ 個矩形進入掃描線：區間 $[xl_i, xr_i]$ 加 $1$ 2. 第 $i$ 個矩形離開掃描線：區間 $[xl_i, xr_i]$ 減 $1$ 3. 查詢整個數線 **非 $0$** 長度總和 ---- - 區間修改: $(1,2)$ - 區間查詢: $(3)$ - $\implies$ 懶標線段樹 ---- - $\text{cnt}$：該區間完整線段個數 - $\text{sum}$：該區間非$0$長度 ```c= struct node { int cnt, sum ; } ``` ---- ### Pull ```c= void pull(int lb, int rb, int idx) { if(seg[idx].cnt > 0) seg[idx].sum = rb - lb + 1 ; else seg[idx].sum = seg[idx*2].sum + seg[idx*2+1].sum ; } ``` ---- ### Push - 有需要嗎？ - $\text{query}$：整個數線 - $\text{modify}$：刪除先前放入的區間 ---- ```c= // by Ccucumber12 #include <iostream> #include <algorithm> #include <cmath> #include <bitset> #include <cstring> #include <string.h> #include <sstream> #include <iomanip> #include <queue> #include <stack> #include <deque> #include <map> #include <set> #include <unordered_set> #include <unordered_map> #include <tuple> #include <vector> #include <random> #include <chrono> using namespace std; #define F first #define S second #define siz(v) ((int)v.size()) #define rs(n) resize(n) #define ALL(v) v.begin(),v.end() #define reset(v) memset((v),0,sizeof(v)) #define EB emplace_back #define MP make_pair #define rep(i,n) for(int i=0;i<(n);i++) #define rep1(i,n) for(int i=1;i<=(n);i++) #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define debug(x) cout << " > " << #x << ':' << x << endl; #define kiyohime ios::sync_with_stdio(false);cin.tie(0); #define endl '\n' using ll = unsigned long long; using pii = pair<int,int>; using pll = pair<ll,ll>; template<typename T> using vec = vector<T>; template<typename T> using Prior = priority_queue<T>; template<typename T> using prior = priority_queue<T, vec<T>, greater<T>>; const int INF = 1e9; const ll LLINF = (ll)4*1e18; const ll MOD = 1e9+7; const double PI = 3.14159265358; const double EPS = 1e-8; const int xx[8] = {0,1,0,-1,1,1,-1,-1}; const int yy[8] = {1,0,-1,0,1,-1,-1,1}; void pmod(ll &a, ll b) {a = (a+b)%MOD;} void mmod(ll &a, ll b) {a = (a-b+MOD)%MOD;} void tmod(ll &a, ll b) {a = (a*b)%MOD;} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ll POW(ll a, ll b) {ll res=1; do{if(b%2)tmod(res,a);tmod(a,a);}while(b>>=1); return res;} template<typename T> T gcd(T a, T b) {return b == 0 ? a : gcd(b, a%b);}; template<typename T> void amax(T &a, T b) {if(a < b) a = b;} template<typename T> void amin(T &a, T b) {if(a > b) a = b;} #define N 100010 struct node{ node *lch, *rch; int val, sum; node () { lch = rch = nullptr; val = sum = 0; } void pull(){ sum = 0; if(lch) sum += lch -> sum; if(rch) sum += rch -> sum; } void modify(int l, int r, int lb, int rb, int v){ if(l <= lb && rb <= r){ val += v; if(val) sum = rb - lb + 1; else pull(); return ; } int mid = lb + rb >> 1; if(!lch) lch = new node(); if(!rch) rch = new node(); if(l <= mid) lch -> modify(l, r, lb, mid, v); if(mid < r) rch -> modify(l, r, mid+1, rb, v); if(val) sum = rb - lb + 1; else pull(); } }; struct segment{ int L, R, H, V; }; void solve(){ int n; cin >> n; vec<segment> v; rep(i, n){ int l, r, u, d; cin >> l >> r >> d >> u; v.EB(segment{l+1, r, d, 1}); v.EB(segment{l+1, r, u, -1}); } sort(ALL(v), [](segment a, segment b){ return a.H < b.H; }); node *root = new node(); int cur = v.front().H; ll ans = 0; for(auto i:v){ if(i.H != cur){ ans += (ll)root -> sum * (i.H - cur); cur = i.H; } root -> modify(i.L, i.R, 1, 1e6, i.V); } ans += (ll)root -> sum * (v.back().H - cur); cout << ans << endl; } int main(){ // kiyohime int T = 1; // cin >> T; while(T--){ solve(); } } ``` --- ## Dynamic Segment Tree ---- ### Problem - 給定 $N$ 個二維平面上的矩形，求聯集面積 - $N \leq 10^6$，$|\text{座標}| \leq 10^9$ ---- ### Discretize - 離散化 - 紀錄區間原始長度當成權重 - 塞進線段樹 ---- ### Copy on Write - 只記錄需要 / 經過的點 - 以指標實作 - 每次操作：$\mathcal{O}(\log C)$ ---- ### Node ```c= struct node { int val ; node *lch, *rch ; void pull() { ... } void modify() { ... } int query() { ... } } ``` ---- ### Pull ```c= void pull() { val = 0 ; if(lch) val += lch -> val ; if(rch) val += rch -> val ; } ``` ---- ### Modify ```c= void modify(int p, int v, int lb, int rb) { if(lb == rb) { val = v ; return ; } if(!lch) lch = new node() ; if(!rch) rch = new node() ; int mid = lb + rb >> 1 ; if(p <= mid) lch -> modify(p, v, lb, mid) ; if(mid < p) rch -> modify(p, v, mid+1, rb) ; pull() ; } ``` ---- ### Query ```c= int query(int l, int r, int lb, int rb) { if(l <= lb && rb <= r) return val ; int mid = lb + rb >> 1 ; int ret = 0 ; if(l <= mid && lch) ret += lch -> query(l, r, lb, mid) ; if(mid < r && rch) ret += rch -> query(l, r, mid+1, rb) ; return ret ; } ``` ---- ### KEY - 拜訪指標前確保存在，避免戳到 $\text{nullptr}$ - 將要做的事好好整理在副函式裡 - 訪問指標內物件記得使用 `->` - 操作完小孩記得 $\text{pull}$ 一下 ---- ### Complexity - Time: $\mathcal{O}(\log C)$ - Space: $\mathcal{O}(\log C)$ new nodes / modify --- ## 2D Segment Tree ---- ### Problem - 給定$N \times N$ 平面，初始值皆為 $0$，請支援以下操作 1. $\text{add x y v}$：將座標 $(x,y)$ 加上 $v$ 2. $\text{query x1 y1 x2 y2}$：詢問該矩形總和 - $N \leq 10^9$，$Q \leq 10^5$ ---- 對於其中一個維度的每一格開一個線段樹 - Add: $\mathcal{O}(\log N)$ - Query: $\mathcal{O}(N\log N)$ ---- - 能否減少 Query 的時間複雜度？ - 將第一個維度多個區間合併在一起？ - 線段樹包線段樹？(樹套樹) ---- - 將第一個維度切成多個區間 (線段樹) - 每個線段樹所代表的區間視為一格 - 對第二維度做線段樹 ----  ---- ### Query - 將第一個維度切成 $\mathcal{O}(\log C)$ 個區間(線段樹) - 對於每個區間(線段樹)，Query第二個維度所需的長度 - 將每個區間的答案合併 - $\mathcal{O}(\log^2 C)$ ---- ### Add - 對於任意座標，第一維度共有 $\mathcal{O}(\log N)$ 個區間包含 - 每個區間再花 $\mathcal{O}(\log N)$ 做修改 - $\mathcal{O}(\log^2 C)$ ---- ### Complexity - Time Complexity: - Add: $\mathcal{O}(\log^2 C)$ - Query: $\mathcal{O}(\log^2 C)$ - Space Complexity: $\mathcal{O}(\log^2 C)$ ---- ```c= struct seg1D { int val = 0; seg1D *lch = nullptr, *rch = nullptr ; void pull() { val = 0 ; if(lch) amax(val, lch -> val) ; if(rch) amax(val, rch -> val) ; } void modify(int x, int p, int lb = 0, int rb = N) { if(lb == rb) { amax(val, p) ; return ; } int mid = lb + rb >> 1; if(x <= mid) { if(!lch) lch = new seg1D ; lch -> modify(x, p, lb, mid) ; } if(mid < x) { if(!rch) rch = new seg1D ; rch -> modify(x, p, mid+1, rb) ; } pull() ; } int query(int l, int r, int lb = 0, int rb = N) { if(l <= lb && rb <= r) return val ; int mid = lb + rb >> 1 ; int ret = 0 ; if(l <= mid && lch) amax(ret, lch -> query(l, r, lb, mid)) ; if(mid < r && rch) amax(ret, rch -> query(l, r, mid+1, rb)) ; return ret ; } }; struct seg2D { seg1D seg; seg2D *lch = nullptr, *rch = nullptr; void modify(int x, int y, int p, int lb = 0, int rb = N) { seg.modify(y, p) ; if(lb == rb) return ; int mid = lb + rb >> 1 ; if(x <= mid) { if(!lch) lch = new seg2D ; lch -> modify(x, y, p, lb, mid) ; } if(mid < x) { if(!rch) rch = new seg2D ; rch -> modify(x, y, p, mid+1, rb) ; } } int query(int xl, int xr, int yl, int yr, int lb = 0, int rb = N) { if(xr < xl || yr < yl) return 0 ; if(xl <= lb && rb <= xr) return seg.query(yl, yr) ; int mid = lb + rb >> 1 ; int ret = 0 ; if(xl <= mid && lch) amax(ret, lch -> query(xl, xr, yl, yr, lb, mid)) ; if(mid < xr && rch) amax(ret, rch -> query(xl, xr, yl, yr, mid+1, rb)) ; return ret ; } }; ``` ---- ### 三維偏序 - 給定 $N$ 個物件，每個物件有三個參數 $X_i, Y_i, Z_i$ - 請問最多可以選幾個物件，使得任意排序後，三個參數皆嚴格遞增 ---- #### 二維偏序 - 最長嚴格遞增子序列 - 依照 $X$ 排序 - 對於每個物件查詢 $[1,Y-1]$ 之間最大DP值 - 將答案更新在 $Y$ - BIT / Segment Tree ---- - 依照 $X$ 排序 - 對於每個物件查詢 $[(1,1) ~ (Y-1, Z-1)]$ 矩形內最大DP值 - 將答案更新再 $(Y,Z)$ - 2D Segment Tree ---- ### D維線段樹 - 樹套樹套樹... - 每次顆線段樹維護一個維度 - Time Complexity: $\mathcal{O}(\log^D C)$ ---- ### Lazy Propagation - 只支援永久懶標：不須往下push - 其他方案： - Quadtree - KD Tree --- ## Persistent Segment Tree ---- ### Problem - 給定數列 $a_1, a_2, a_3, \dots a_N$，請支援以下操作 1. $\text{add x v}$：將 $a_x$ 加上 $v$ 2. $\text{query l r k}$: 詢問第 $k$ 次修改後 ---- ### Offline - 正常操作，在第 $k$ 次操作後記錄需要的答案 - 整理後輸出 - $\mathcal{O}(Q\log N)$ ---- ### Online - 回到過去？ - 紀錄每個版本的線段樹 - Space Complexity: $\mathcal{O}(QN)$ ---- ### Copy on Write - 只備份改變的那些點 - 每一個新的版本代表一個新的root - 每次修改 $\mathcal{O}(\log N)$ 個節點 - 總共增加 $\mathcal{O}(Q\log N)$ 個空間 - Space Complexity: $\mathcal{O}(N + Q\log N)$ ---- ### Persistent Segment Tree - 持久化線段樹 - 主席樹 ----  ---- ```cpp= struct node{ node *lch, *rch; int val; node () { lch = rch = nullptr; val = 0; } void pull(){ val = lch -> val + rch -> val; } }; void build(int l, int r, node *&p){ p = new node(); if(l == r) return ; int mid = (l + r) >> 1; build(l, mid, p -> lch); build(mid+1, r, p -> rch); p -> pull(); } void modify(int pos, int lb, int rb, node *pre, node *&cur){ cur = new node(); if(lb == rb) { cur -> val = pre -> val + 1; return ; } cur -> lch = pre -> lch; cur -> rch = pre -> rch; int mid = (lb + rb) >> 1; if(pos <= mid) modify(pos, lb, mid, pre -> lch, cur -> lch); if(mid < pos) modify(pos, mid+1, rb, pre -> rch, cur -> rch); cur -> pull(); } int query(int val, int lb, int rb, node *l, node *r){ if(lb == rb) return lb; int k = r->lch->val - l->lch->val; int mid = (lb + rb) >> 1; if(val <= k) return query(val, lb, mid, l->lch, r->lch); else return query(val-k, mid+1, rb, l->rch, r->rch); } ``` ---- ### 區間第 k 小 - 給定數列 $a_1, a_2, a_3, \dots a_N$，請支援以下操作 1. $\text{query l r k}$：詢問區間 $[a_l,\ a_r]$ 中第 $k$ 小的數字 - $N,Q,a_i \leq 10^6$ ---- 只詢問一次 $[1, N]$ - 相對位置不重要 - 各個數字有多少個 - **值域線段樹** ---- ### 值域線段樹 - 葉節點 $\text{seg}[i]$ 代表數字 $i$ 有多少個 - 區間 $\text{seg}[L,R]$ 代表數字介於 $[L,R]$ 有多少個 - 第 $k$ 小：葉節點 $x$ 的左邊累積到 $k-1$ - **二分搜** ---- 只詢問區間 $[1, R]$ - 依序插入第 $i$ 個數 - 線段樹紀錄每次插入第 $i$ 個數的結果 - **持久化線段樹** ---- 詢問區間 $[L, R]$ - 第 $L$ 個版本到第 $R$ 個版本 - 這些版本的數字個數 - 版本$R$ $-$ 版本$(L-1)$ ---- ```c= // by Ccucumber12 #include <bits/stdc++.h> using namespace std; #define F first #define S second #define siz(v) ((int)v.size()) #define rs(n) resize(n) #define ALL(v) v.begin(),v.end() #define reset(v) memset((v),0,sizeof(v)) #define EB emplace_back #define MP make_pair #define rep(i,n) for(int i=0;i<(n);i++) #define rep1(i,n) for(int i=1;i<=(n);i++) #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define debug(x) cout << " > " << #x << ':' << x << endl; #define kiyohime ios::sync_with_stdio(false);cin.tie(0); #define endl '\n' using ll = unsigned long long; using pii = pair<int,int>; using pll = pair<ll,ll>; template<typename T> using vec = vector<T>; template<typename T> using Prior = priority_queue<T>; template<typename T> using prior = priority_queue<T, vec<T>, greater<T>>; const int INF = 1e9; const ll LLINF = (ll)4*1e18; const ll MOD = 1e9+7; const double PI = 3.14159265358; const double EPS = 1e-8; const int xx[8] = {0,1,0,-1,1,1,-1,-1}; const int yy[8] = {1,0,-1,0,1,-1,-1,1}; void pmod(ll &a, ll b) {a = (a+b)%MOD;} void mmod(ll &a, ll b) {a = (a-b+MOD)%MOD;} void tmod(ll &a, ll b) {a = (a*b)%MOD;} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ll POW(ll a, ll b) {ll res=1; do{if(b%2)tmod(res,a);tmod(a,a);}while(b>>=1); return res;} template<typename T> T gcd(T a, T b) {return b == 0 ? a : gcd(b, a%b);}; template<typename T> void amax(T &a, T b) {if(a < b) a = b;} template<typename T> void amin(T &a, T b) {if(a > b) a = b;} #define N 100010 vec<int> discrete(vec<int> &v){ vec<int> dct; for(auto i:v) dct.EB(i); sort(ALL(dct)); dct.rs(unique(ALL(dct)) - dct.begin()); for(auto &i:v) i = int(lower_bound(ALL(dct), i) - dct.begin() + 1); return dct; } struct node{ node *lch, *rch; int val; node () { lch = rch = nullptr; val = 0; } void pull(){ val = lch -> val + rch -> val; } }; void build(int l, int r, node *&p){ p = new node(); if(l == r) return ; int mid = (l + r) >> 1; build(l, mid, p -> lch); build(mid+1, r, p -> rch); } void modify(int pos, int lb, int rb, node *pre, node *&cur){ cur = new node(); if(lb == rb) { cur -> val = pre -> val + 1; return ; } cur -> lch = pre -> lch; cur -> rch = pre -> rch; int mid = (lb + rb) >> 1; if(pos <= mid) modify(pos, lb, mid, pre -> lch, cur -> lch); if(mid < pos) modify(pos, mid+1, rb, pre -> rch, cur -> rch); cur -> pull(); } int query(int val, int lb, int rb, node *l, node *r){ if(lb == rb) return lb; int k = r->lch->val - l->lch->val; int mid = (lb + rb) >> 1; if(val <= k) return query(val, lb, mid, l->lch, r->lch); else return query(val-k, mid+1, rb, l->rch, r->rch); } void solve(){ int n, m; cin >> n >> m; vec<int> v(n), dct; for(auto &i:v) cin >> i; dct = discrete(v); vec<node*> ver(n+1); int mxn = 1; while(mxn < siz(dct)) mxn <<= 1; build(1, mxn, ver[0]); rep(i, n) modify(v[i], 1, mxn, ver[i], ver[i+1]); int ipl, ipr, ipk; while(m--){ cin >> ipl >> ipr >> ipk; cout << dct[query(ipk, 1, mxn, ver[ipl-1], ver[ipr]) - 1] << endl; } } int main(){ // kiyohime int T = 1; // cin >> T; while(T--){ solve(); } } ``` --- ## Treap ---- - Tree + Heap - 平衡樹 - Merge-Split Treap - Splay - ... ---- ### Binary Search Tree - Time Complexity: $\mathcal{O}(h)$ - 高度太高 - 加入變數使得高度期望是 $\mathcal{O}(\log N)$ ---- ### Key & Pri - Key: 存入的數字，維護BST - 任意Key大於等於左子樹的Key - 任意Key小於等於右子樹的Key - Pri: 隨機變數，維護heap - 任意Pri大於所有子樹的Pri ---- ### 隨機Pri - 若隨機給予 Pri 的值 - 期望高度為 $\mathcal{O}(\log N)$ - Proof: <\<Introduction to Algorithms>> ---- ### 其他功能 - size: 區間數字個數 - count: 數字存在個數 - rank: 詢問數字第幾大 - kth: 詢問第 $k$ 大的數字 - 各種集合操作 - ... ---- ```c= struct Treap { struct node { int val, pri, sz; node *lch, *rch; node (int _val) { val = _val ; sz = 1 ; pri = rng() ; lch = rch = nullptr ; } void pull() { sz = 1 ; if(lch) sz += lch -> sz ; if(rch) sz += rch -> sz ; } }; node *rt = nullptr ; int fs (node *a) { return a ? a -> sz : 0 ; } node *merge(node *a, node *b) { if(!a || !b) return a ? a : b ; if(a -> pri < b -> pri) { a -> rch = merge(a -> rch, b) ; a -> pull() ; return a ; } else { b -> lch = merge(a, b -> lch) ; b -> pull() ; return b ; } } void split(node *T, node *&a, node *&b, int p) { if(!T) { a = b = nullptr ; return ; } if(T -> val > p) { b = T ; split(T -> lch, a, b -> lch, p) ; b -> pull() ; } else { a = T ; split(T -> rch, a -> rch, b, p) ; a -> pull() ; } } void splitSz(node *T, node *&a, node *&b, int p) { if(!T) { a = b = nullptr ; return ; } if(fs(T -> lch) < p) { a = T ; splitSz(T -> rch, a -> rch, b, p - fs(T -> lch) - 1); a -> pull() ; } else { b = T ; splitSz(T -> lch, a, b -> lch, p) ; b -> pull() ; } } void insert(int p) { node *a = new node(p), *b; split(rt, rt, b, p) ; rt = merge(rt, a) ; rt = merge(rt, b) ; } void erase(int p) { node *a, *b ; split(rt, rt, a, p - 1) ; splitSz(a, a, b, 1) ; delete(a) ; rt = merge(rt, b) ; } int count(int p) { node *a, *b ; split(rt, rt, b, p) ; split(rt, rt, a, p - 1) ; int ret = fs(a) ; rt = merge(rt, a) ; rt = merge(rt, b) ; return ret ; } int rank(int p) { node *a, *b; split(rt, rt, b, p) ; split(rt, rt, a, p - 1) ; int ret = fs(rt) + 1 ; rt = merge(rt, a); rt = merge(rt, b); return ret ; } int kth(int p) { node *a, *b ; splitSz(rt, rt, b, p) ; splitSz(rt, rt, a, p - 1) ; int ret = a -> val ; rt = merge(rt, a) ; rt = merge(rt, b) ; return ret ; } int prev(int p) { node *a, *b ; split(rt, rt, b, p - 1) ; splitSz(rt, rt, a, fs(rt) - 1) ; int ret = a -> val ; rt = merge(rt, a) ; rt = merge(rt, b) ; return ret ; } int next(int p) { node *a, *b ; split(rt, rt, a, p) ; splitSz(a, a, b, 1) ; int ret = a -> val ; a = merge(a, b) ; rt = merge(rt, a) ; return ret ; } }; ``` ---- ### 處理線性資料 - Insert the data by merging the treaps one by one - Inorder will be the linear data, while the pri will make it balanced. ---- ### 功能 - 將任意區間切下 - 將任意區間插入 - 將任意區間反轉 - 將任意區間旋轉 - 各種區間操作 - ... ---- ```c= struct Treap{ Treap *l, *r; int val, pri, size; bool revTag; Treap (int _v) : l (nullptr), r (nullptr), val (_v), pri (rng()), size (1), revTag (false) {} void rev(){ swap(l, r); revTag ^= 1; } void push(){ if(revTag){ if(l) l -> rev(); if(r) r -> rev(); revTag = false; } } void pull(){ size = 1; if(l) size += l -> size; if(r) size += r -> size; } }; int getSize(Treap *p){ return p ? p -> size : 0; } Treap *merge (Treap *a, Treap *b){ if(!a || !b) return a ? a : b; if(a -> pri < b -> pri){ a -> push(); a -> r = merge(a -> r, b); a -> pull(); return a; } else { b -> push(); b -> l = merge(a, b -> l); b -> pull(); return b; } } void splitSize (Treap *p, Treap *&a, Treap *&b, int k){ if(!p) { a = b = nullptr; return; } p -> push(); if(getSize(p -> l) < k){ a = p; splitSize(p -> r, a -> r, b, k - getSize(p->l) - 1); a -> pull(); } else { b = p; splitSize(p -> l, a, b -> l, k); b -> pull(); } } void rev(Treap *&p, int l, int r){ Treap *a, *b, *c; splitSize(p, a, c, r); splitSize(a, a, b, l-1); b -> rev(); p = merge(merge(a, b), c); } void dfs(Treap *p){ // in-order if(!p) return ; p -> push(); if(p -> l) dfs(p -> l); cout << p -> val << ' ' ; if(p -> r) dfs(p -> r); } ``` --- ## Credit - 演算法筆記 - http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f220f2d6b33ae091978ebf59d2af5908bc8190b51