文章目錄

• 左偏樹
• 左偏樹的合并(merge)操作
• 例題
• • 羅馬游戲
  • [Apio2012]dispatching
  • [JLOI2015]城池攻占
  • [Baltic2004]sequence

左偏樹

左偏樹是一個堆，而且是一個可并堆，所以一定有權值的限制

以小根堆為例，那么必須滿足節點權值小于左右兒子權值，即val[i]<val[lson[i]] val[i]<val[rson[i]]

為了維護左偏樹的時間復雜度，就要設計一些左偏樹獨有的工具，定義

• 外節點：滿足左右兒子至少有一個沒有的點
• 距離dis[i]：點$i$到離它最近的一個外節點的距離；特別的，空節點的距離為$?1$，外節點本身距離為$0$

左偏樹，樹如其名，向左偏的樹

也就是說左邊要“重一點”，但這個重不是常見的子樹大小或者高度，而是我們定義的dis

• 對于左偏樹的每個點$i$，滿足dis[lson[i]]>=dis[rson[i]]

完全有可能，左兒子只有一個點，右兒子是一條鏈：不管是左兒子的一個點還是右兒子一條鏈上的點都符合外節點定義，所以dis都是$0$

考慮由下向上更新距離數組，即dis[i]=min(dis[lson[i]],dis[rson[i]])+1

由于左偏樹的性質，右兒子距離一定是小的，所以左偏樹的更新直接就是從右兒子處更新

• dis[i]=dis[rson[i]]+1

左偏樹特殊距離的定義，就保證了左偏樹的時間復雜度

• 節點數為$n$的樹，樹根的$dis\le \log (n+1)?1$

一個點的距離大于$x$，意味著$x?1$層內都是滿二叉樹

左偏樹的合并(merge)操作

左偏樹最重要的，或者說特色，就是它的合并操作

有了以上的理論基礎，結合fhq-treap的返回根合并操作，左偏樹的合并還是很好寫的

struct node { int l, r, val, dis; } t[maxn]; int merge( int x, int y ) {if( ! x or ! y ) return x + y;if( t[x].val > t[y].val ) swap( x, y );t[x].r = merge( t[x].r, y );if( t[t[x].l].dis < t[t[x].r].dis ) swap( t[x].l, t[x].r );t[x].dis = t[t[x].r].dis + 1;return x; } int lson[maxn], rson[maxn], val[maxn], dis[maxn]; int merge( int x, int y ) {if( ! x or ! y ) return x + y;if( val[x] < val[y] ) swap( x, y );rson[x] = merge( rson[x], y );if( dis[lson[x]] < dis[rson[x]] ) swap( lson[x], rson[x] );dis[x] = dis[rson[x]] + 1;return x; }

例題

羅馬游戲

luogu 2713

這就是比較板的題了，初始時，把每個士兵當成一個左偏樹，合并就是兩個士兵的左偏樹合并

殺士兵，就是去掉左偏樹的根節點，直接合并左右兒子即可

但是怎么找士兵所在的兵團呢？——并查集！

#include <cstdio> #include <iostream> using namespace std; #define maxn 1000005 struct node { int l, r, val, dis; } t[maxn]; bool vis[maxn]; int f[maxn]; int n, m;int find( int x ) { return x == f[x] ? x : f[x] = find( f[x] ); }int merge( int x, int y ) {if( ! x or ! y ) return x + y;if( t[x].val > t[y].val ) swap( x, y );t[x].r = merge( t[x].r, y );if( t[t[x].l].dis < t[t[x].r].dis ) swap( t[x].l, t[x].r );t[x].dis = t[t[x].r].dis + 1;return x; }int main() {scanf( "%d", &n );t[0].dis = -1;for( int i = 1;i <= n;i ++ ) {scanf( "%d", &t[i].val );f[i] = i;}scanf( "%d", &m );char opt[5]; int i, j;while( m -- ) {scanf( "%s", opt );if( opt[0] == 'M' ) {scanf( "%d %d", &i, &j );if( vis[i] or vis[j] ) continue;i = find( i ), j = find( j );if( i ^ j ) f[j] = f[i] = merge( i, j );}else {scanf( "%d", &i );if( vis[i] ) printf( "0\n" );else {i = find( i );vis[i] = 1;printf( "%d\n", t[i].val );f[i] = f[t[i].l] = f[t[i].r] = merge( t[i].l, t[i].r );/*就算殺了根節點代表的這個士兵也要更新士兵的并查集集合因為可能有些士兵跨過了根節點的左右兒子直接并查集是接在根節點并查集的下面的find的時候是會跳到根節點的并查集點的*/}}}return 0; }

[Apio2012]dispatching

BZOJ 2809

dfs樹從下往上合并

每次丟掉最大的$C_i$即可

同樣別忘了并查集

#include <cstdio> #include <vector> #include <iostream> using namespace std; #define maxn 100005 #define int long long vector < int > G[maxn]; int lson[maxn], rson[maxn], dis[maxn], f[maxn], L[maxn], C[maxn]; int n, m, root; long long ans;int find( int x ) { return f[x] == x ? x : f[x] = find( f[x] ); }int merge( int x, int y ) {if( ! x or ! y ) return x + y;if( C[x] < C[y] ) swap( x, y );rson[x] = merge( rson[x], y );if( dis[lson[x]] < dis[rson[x]] ) swap( lson[x], rson[x] );dis[x] = dis[rson[x]] + 1;return x; }pair < int, int > dfs( int u ) {int cnt = 1, sum = C[u];for( auto v : G[u] ) {pair < int, int > son = dfs( v );cnt += son.first, sum += son.second;int x = find( u ), y = find( v );root = f[u] = f[v] = merge( x, y );while( sum > m ) {sum -= C[root], cnt --;f[root] = f[lson[root]] = f[rson[root]] = merge( lson[root], rson[root] );root = f[root];}ans = max( ans, L[u] * cnt );}ans = max( ans, L[u] * cnt );return make_pair( cnt, sum ); }signed main() {scanf( "%lld %lld", &n, &m );for( int i = 1, B;i <= n;i ++ ) {scanf( "%lld %lld %lld", &B, &C[i], &L[i] );G[B].push_back( i );f[i] = i;}dis[0] = -1;dfs( 1 );printf( "%lld\n", ans );return 0; }

[JLOI2015]城池攻占

luogu 3261

初始時，將每一座城市當成一個左偏樹，并把在該城市的士兵在左偏樹上完成合并

與上一題一樣的，從下往上合并左偏樹，把所有兒子的騎士聚集到當前根節點城市

把戰斗力不足的扔掉，所以需要小根堆

利用初末城市的深度差，巧妙計算出每個騎士能攻占的城市數量

至于城市對騎士的戰斗力影響，一樣的整體懶標記，碰到了再下傳

#include <cstdio> #include <vector> #include <iostream> using namespace std; #define int long long #define maxn 300005 vector < int > G[maxn]; struct node { int lson, rson, dis, val, add, mul; }t[maxn]; int root[maxn], h[maxn], a[maxn], v[maxn], c[maxn]; int ans1[maxn], ans2[maxn], dep[maxn]; int n, m;void modify( int x, int mul, int add ) {if( ! x ) return;t[x].val *= mul;t[x].val += add;t[x].mul *= mul;t[x].add *= mul;t[x].add += add; }void pushdown( int x ) { if( ! x ) return;modify( t[x].lson, t[x].mul, t[x].add );modify( t[x].rson, t[x].mul, t[x].add );t[x].mul = 1;t[x].add = 0; }int merge( int x, int y ) {if( ! x or ! y ) return x + y;pushdown( x );pushdown( y );if( t[x].val > t[y].val ) swap( x, y );t[x].rson = merge( t[x].rson, y );if( t[t[x].lson].dis < t[t[x].rson].dis ) swap( t[x].lson, t[x].rson );t[x].dis = t[t[x].rson].dis + 1;return x; }void dfs( int u, int fa ) {dep[u] = dep[fa] + 1;for( auto v : G[u] ) {dfs( v, u );root[u] = merge( root[u], root[v] );//將所有從子樹的管轄城市中存活到u城市的騎士進行合并 }while( root[u] and t[root[u]].val < h[u] ) {//從最小殺傷力騎士開始 將所有在u城市死亡的騎士剔除 并記錄最后答案 pushdown( root[u] );ans1[u] ++;ans2[root[u]] = dep[c[root[u]]] - dep[u];//騎士能攻占的數量巧妙利用初末深度差 最開始的城市深度-u的深度 root[u] = merge( t[root[u]].lson, t[root[u]].rson ); }if( a[u] ) modify( root[u], v[u], 0 );else modify( root[u], 1, v[u] ); }signed main() {scanf( "%lld %lld", &n, &m );for( int i = 1;i <= n;i ++ ) scanf( "%lld", &h[i] );for( int i = 2, f;i <= n;i ++ ) {scanf( "%lld %lld %lld", &f, &a[i], &v[i] );G[f].push_back( i );}t[0].dis = -1;//在每一座城市都建立一個左偏樹 for( int i = 1;i <= m;i ++ ) {scanf( "%lld %lld", &t[i].val, &c[i] );root[c[i]] = merge( root[c[i]], i );//將在同一座城市的騎士在左偏樹上體現合并 //root[i]:在城市i的左偏樹的最小殺傷力騎士的編號 }dfs( 1, 0 );//搜城 從下往上爬 while( root[1] ) {/*最后在總城市根1的騎士答案還未計算 暴力彈出所有存活的騎士 攻占的數量就是初始城市到1號超級城市一路經過的城市也就是深度*/ ans2[root[1]] = dep[c[root[1]]];root[1] = merge( t[root[1]].lson, t[root[1]].rson );}for( int i = 1;i <= n;i ++ ) printf( "%lld\n", ans1[i] );for( int i = 1;i <= m;i ++ ) printf( "%lld\n", ans2[i] );return 0; }

[Baltic2004]sequence

BZOJ 1367

給定$n$，以及長度為$n$的整數序列$a_1,...,a_n$，你需要構造一個嚴格上升的長度為$n$整數序列$t_1,...,t_n$，定義$R=|t_1?a_1|+...+|t_i?a_i|+...+|t_n?a_n|$，求最小的$R$

$n\le 10^6$

---

假設是構造不下降序列

考慮兩種特殊的序列

• $a_1\le a_2\le ...\le a_n$，直接讓$t_i=a_i$，最后答案就是$0$
• $a_1\ge a_2\ge ...\ge a_n$，直接讓$t_1=a_{mid}$（序列的中位數）

現在考慮一般形式的$a$

將$a$序列劃分成這兩種特殊序列的若干段

考慮$1...i$的答案為$w_1,...w_i$，現在考慮$i+1$，先讓$w_{i+1}=a_{i+1}$

然后就要根據第二種特殊序列，進行合并，如果$w_i\ge w_{i+1}$，就合并后$w_i=w_{i+1}=$中位數，直到$w_j<w_{i+1}$

這個中位數是參與合并的$w$中的中位數，不是整體的中位數

用左偏樹維護一個$siz$大小即可

#include <cstdio> #include <iostream> using namespace std; #define maxn 1000005 struct node {int lson, rson, val, siz, dis; }t[maxn]; int n, cnt; int root[maxn], L[maxn], R[maxn], a[maxn];int merge( int x, int y ) {if( ! x or ! y ) return x + y;if( t[x].val < t[y].val ) swap( x, y );t[x].rson = merge( t[x].rson, y );t[x].siz = t[t[x].lson].siz + t[t[x].rson].siz + 1;if( t[t[x].lson].dis < t[t[x].rson].dis )swap( t[x].lson, t[x].rson );t[x].dis = t[t[x].rson].dis + 1;return x; }long long Fabs( long long x ) {return x < 0 ? -x : x; }int NewNode( int x ) {t[++ cnt].val = x;t[cnt].siz = 1;t[cnt].lson = t[cnt].rson = t[cnt].dis = 0;return cnt; }int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ )scanf( "%d", &a[i] ), a[i] -= i;t[0].dis = -1;int ip = 0;for( int i = 1;i <= n;i ++ ) {++ ip;L[ip] = R[ip] = i;root[ip] = NewNode( a[i] );while( ip > 1 and t[root[ip - 1]].val > t[root[ip]].val ) {root[ip - 1] = merge( root[ip - 1], root[ip] );R[ip - 1] = R[ip];ip --;while( t[root[ip]].siz * 2 > R[ip] - L[ip] + 2 )root[ip] = merge( t[root[ip]].lson, t[root[ip]].rson );}}long long ans = 0;while( ip ) {int val = t[root[ip]].val;for( int i = L[ip];i <= R[ip];i ++ )ans += Fabs( 1ll * val - a[i] );ip --;}printf( "%lld\n", ans );return 0; }

總結

以上是生活随笔為你收集整理的【学习笔记】浅谈短小可爱的左偏树（可并堆）的全部內容，希望文章能夠幫你解決所遇到的問題。

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