数据结构与算法：有序表（四）：笛卡尔树与 Treap-北京尧图网络

前言越来越难了……希望区域赛有个好结果吧加油加油加油一、笛卡尔树1.性质笛卡尔树有两个属性 key 和 value一般默认 key 没有重复值。此时笛卡尔树满足 key 按搜索二叉树组织value 按堆组织。2.建立在笛卡尔树的建立过程中用单调栈维护节点的 value即树上从顶到底的一条链。所以如果要求 value 是小根堆那么就让单调栈内大压小。每当有节点入栈那么就让其成为栈顶节点的右孩子。在上图中例子在考虑完前三个位置后此时单调栈内是如图所示所以就在树上建出了这条链。当 (4,4) 这个节点来到时由于 4 小于 8 和 6此时就让最后一个弹出的节点和其父亲断连让其作为左孩子挂在当前节点的下面然后再让当前节点挂在此时的栈顶节点的右孩子上的。所以此时 (2,6) 和 (3,8) 这条链就需要成为 (4,4) 的左孩子然后 (4,4) 成为 (1,3) 的右孩子。之后当 (5,7) 来到时还是成为 (4,4) 的右孩子。可以发现由于后来的 key 肯定比前面的大所以在插入节点时往左挂必然就满足搜索二叉树的性质。又因为是单调栈所以上方的 value 必然小于下方的 value也满足堆的性质。在 (6,1) 来到时此时所有的节点都需要弹出那么 (6,1) 就成为当前树的头节点其他节点都挂在其左子树上。在 (7,5) 来到时还是直接成为 (6,1) 的右孩子。在 (8,2) 来到时就让 (7,5) 挂在其左子树上然后其成为 (6,1) 的右孩子整个过程结束。此时栈中最底下的节点就是笛卡尔树的头节点。二、Treap 树Treap 树就是笛卡尔树key 还是按二叉搜索树组织priority 表示节点优先级随机生成按堆组织。当 priority 不满足堆的性质时就通过左旋或右旋一直往上调整即可。删除时若要删除节点是叶子那么就直接删除。若有左无右或有右五左那么就让那个孩子接替自己即可。而若两边都有那么就通过左旋或右旋让 priority 大的那个孩子上来然后再去子树删除这个节点。三、笛卡尔树题目1.笛卡尔树#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题注意特判 *不要红温不要急躁耐心一点 *WA了不要立马觉得是思路不对先耐心找反例 */ #define endl \n #define dbg(x) cout#xendl;coutxendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; vectorinta(n1); for(int i1;in;i) { cina[i]; } vectorintleft(n1); vectorintright(n1); vectorintstk(n1); for(int i1,top0,pos0;in;i){ postop; while(pos0a[stk[pos]]a[i]){ pos--; } if(pos0){ right[stk[pos]]i; } if(postop){ left[i]stk[pos1]; } stk[pos]i; toppos; } ll ans10,ans20; for(int i1;in;i) { ans1^1ll*i*(left[i]1); ans2^1ll*i*(right[i]1); } coutans1 ans2endl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }在构建的过程中每次用 pos 虚拟弹出节点。最后若还有节点没弹出就修改其右孩子若有东西弹出了就设置左孩子即可。2.树的序#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题注意特判 *不要红温不要急躁耐心一点 *WA了不要立马觉得是思路不对先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; vectorintp(n1); for(int i1;in;i) { cinp[i]; } vectorinta(n1); for(int i1;in;i) { a[p[i]]i; } vectorintleft(n1); vectorintright(n1); vectorintstk(n1); for(int i1,top0,pos0;in;i){ postop; //small heap while(pos0a[stk[pos]]a[i]){ pos--; } if(pos0){ right[stk[pos]]i; } if(postop){ left[i]stk[pos1]; } stk[pos]i; toppos; } auto dfs[](auto self,int u)-void { coutu ; if(left[u]) { self(self,left[u]); } if(right[u]) { self(self,right[u]); } }; dfs(dfs,p[1]); } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }对于建出的这棵树其实直接先序遍历一下就是字典序最小的结果。但由于可能给定的序列就是单调的此时就会导致每次建树的复杂度过大需要考虑优化。由于笛卡尔树建树的复杂度是线性的所以考虑用笛卡尔树优化。由于原来的树中的节点 x必然有其祖先节点出现的位置都在 x 出现位置的前面。那么就可以将下标看作时间戳此时就要求时间戳小的在树的上面。又因为笛卡尔树是权值维度 key 按堆组织时间戳维度按二叉搜索树组织而在这里需要让权值按二叉搜索树组织时间戳按堆组织所以交换一下构建笛卡尔树即可。3.E. Yet Another Array Counting Problem#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题注意特判 *不要红温不要急躁耐心一点 *WA了不要立马觉得是思路不对先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; templateclass T constexpr T power(T a, ll b) { T res 1; for (; b ! 0; b / 2, a * a) { if (b 1) { res * a; } } return res; } templateint M struct ModInt { public: constexpr ModInt() : x(0) {} templatetypename T constexpr ModInt(T x_) { T v x_ % M; if (v 0) { v M; } x v; } constexpr int val() const { return x; } constexpr ModInt operator() { x; if (x M) { x 0; } return *this; } constexpr ModInt operator(int) { ModInt res *this; (*this); return res; } constexpr ModInt operator--() { if (x 0) { x M - 1; } else { x--; } return *this; } constexpr ModInt operator--(int) { ModInt res *this; --(*this); return res; } constexpr ModInt operator-() const { ModInt res; res.x (x 0 ? 0 : M - x); return res; } constexpr ModInt inv() const { return power(*this, M - 2); } constexpr ModInt operator*(const ModInt rhs) { x ll(x) * rhs.val() % M; return *this; } constexpr ModInt operator(const ModInt rhs) { x rhs.val(); if (x M) { x - M; } return *this; } constexpr ModInt operator-(const ModInt rhs) { x - rhs.val(); if (x 0) { x M; } return *this; } constexpr ModInt operator/(const ModInt rhs) { return *this * rhs.inv(); } friend constexpr ModInt operator*(ModInt lhs, const ModInt rhs) { lhs * rhs; return lhs; } friend constexpr ModInt operator(ModInt lhs, const ModInt rhs) { lhs rhs; return lhs; } friend constexpr ModInt operator-(ModInt lhs, const ModInt rhs) { lhs - rhs; return lhs; } friend constexpr ModInt operator/(ModInt lhs, const ModInt rhs) { lhs / rhs; return lhs; } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator!(ModInt lhs, const ModInt rhs) { return lhs.val() ! rhs.val(); } friend constexpr std::istream operator(std::istream is, ModInt a) { ll i; is i; a i; return is; } friend constexpr std::ostream operator(std::ostream os, const ModInt a) { return os a.val(); } private: int x; }; templateint M, typename T ModIntM struct Comb { vectorT fac; vectorT inv; Comb(int n) { fac.assign(n, 1); for(int i1;in;i) { fac[i]fac[i-1]*i; } inv.assign(n, 1); inv[n-1]fac[n-1].inv(); for(int in-2;i0;i--) { inv[i]inv[i1]*(i1); } } templatestd::signed_integral U T P(U n, U m) { if(nm) { return 0; } return fac[n] * inv[n - m]; } templatestd::signed_integral U T C(U n, U m) { if(nm||m0) { return 0; } return fac[n] * inv[n - m] * inv[m]; } }; //power函数切记强转成 Z !!!!! constexpr int M 1e97; using Z ModIntM; constexpr int N 2e55; CombMcomb(N); templatestd::signed_integral U Z P(U n, U m) { return comb.P(n, m); } templatestd::signed_integral U Z C(U n, U m) { return comb.C(n, m); } void solve() { int n,m; cinnm; vectorinta(n1); for(int i1;in;i) { cina[i]; } vectorintleft(n1); vectorintright(n1); vectorintstk(n1); for(int i1,top0,pos0;in;i){ postop; //big heap while(pos0a[stk[pos]]a[i]){ pos--; } if(pos0){ right[stk[pos]]i; } if(postop){ left[i]stk[pos1]; } stk[pos]i; toppos; } int rootstk[1]; vectorvectorZdp(n1,vectorZ(m1)); for(int j0;jm;j) { dp[0][j]1; } auto dfs[](auto self,int u)-void { if(left[u]) { self(self,left[u]); } if(right[u]) { self(self,right[u]); } for(int j1;jm;j) { dp[u][j]dp[u][j-1]dp[left[u]][j-1]*dp[right[u]][j]; } }; dfs(dfs,root); coutdp[root][m]endl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }这里就有一个性质笛卡尔树的 LCA 就是区间 RMQ。那么在对原数组建立大根堆组织的笛卡尔树后此时每个区间的最左端最大值就是区间两端点在笛卡尔树中的 LCA。那么若此时的根节点选择了数字 x即这个位置在 b 数组中是 x那么之后左孩子代表的位置就只能填小于 x 的数右孩子代表的位置就只能填小于等于 x 的数。这个的方案数可以在 O(nm) 内通过树型 dp 解决。在去笛卡尔树上 dp 时考虑定义 dp[u][j] 为 u 节点值小于等于 j 的方案数。那么每次构建完每个节点值为 x 的方案数时求一下前缀和即可。4.PERIODNI这个题就展示了笛卡尔树划分可能性的用法了。#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题注意特判 *不要红温不要急躁耐心一点 *WA了不要立马觉得是思路不对先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; templateclass T constexpr T power(T a, ll b) { T res 1; for (; b ! 0; b / 2, a * a) { if (b 1) { res * a; } } return res; } templateint M struct ModInt { public: constexpr ModInt() : x(0) {} templatetypename T constexpr ModInt(T x_) { T v x_ % M; if (v 0) { v M; } x v; } constexpr int val() const { return x; } constexpr ModInt operator() { x; if (x M) { x 0; } return *this; } constexpr ModInt operator(int) { ModInt res *this; (*this); return res; } constexpr ModInt operator--() { if (x 0) { x M - 1; } else { x--; } return *this; } constexpr ModInt operator--(int) { ModInt res *this; --(*this); return res; } constexpr ModInt operator-() const { ModInt res; res.x (x 0 ? 0 : M - x); return res; } constexpr ModInt inv() const { return power(*this, M - 2); } constexpr ModInt operator*(const ModInt rhs) { x ll(x) * rhs.val() % M; return *this; } constexpr ModInt operator(const ModInt rhs) { x rhs.val(); if (x M) { x - M; } return *this; } constexpr ModInt operator-(const ModInt rhs) { x - rhs.val(); if (x 0) { x M; } return *this; } constexpr ModInt operator/(const ModInt rhs) { return *this * rhs.inv(); } friend constexpr ModInt operator*(ModInt lhs, const ModInt rhs) { lhs * rhs; return lhs; } friend constexpr ModInt operator(ModInt lhs, const ModInt rhs) { lhs rhs; return lhs; } friend constexpr ModInt operator-(ModInt lhs, const ModInt rhs) { lhs - rhs; return lhs; } friend constexpr ModInt operator/(ModInt lhs, const ModInt rhs) { lhs / rhs; return lhs; } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator!(ModInt lhs, const ModInt rhs) { return lhs.val() ! rhs.val(); } friend constexpr std::istream operator(std::istream is, ModInt a) { ll i; is i; a i; return is; } friend constexpr std::ostream operator(std::ostream os, const ModInt a) { return os a.val(); } private: int x; }; templateint M, typename T ModIntM struct Comb { vectorT fac; vectorT inv; Comb(int n) { fac.assign(n, 1); for(int i1;in;i) { fac[i]fac[i-1]*i; } inv.assign(n, 1); inv[n-1]fac[n-1].inv(); for(int in-2;i0;i--) { inv[i]inv[i1]*(i1); } } templatestd::signed_integral U T P(U n, U m) { if(nm) { return 0; } return fac[n] * inv[n - m]; } templatestd::signed_integral U T C(U n, U m) { if(nm||m0) { return 0; } return fac[n] * inv[n - m] * inv[m]; } }; //power函数切记强转成 Z !!!!! constexpr int M 1e97; using Z ModIntM; constexpr int N 1e65; CombMcomb(N); templatestd::signed_integral U Z P(U n, U m) { return comb.P(n, m); } templatestd::signed_integral U Z C(U n, U m) { return comb.C(n, m); } void solve() { int n,k; cinnk; vectorinta(n1); for(int i1;in;i) { cina[i]; } vectorintleft(n1); vectorintright(n1); vectorintstk(n1); for(int i1,top0,pos0;in;i){ postop; //small heap while(pos0a[stk[pos]]a[i]){ pos--; } if(pos0){ right[stk[pos]]i; } if(postop){ left[i]stk[pos1]; } stk[pos]i; toppos; } int rootstk[1]; auto calc[](int n,int m,int k)-Z { return C(n,k)*C(m,k)*comb.fac[k]; }; vectorintsiz(n1); vectorvectorZdp(n1,vectorZ(k1)); dp[0][0]1; auto dfs[](auto self,int u,int fa)-void { siz[u]1; if(left[u]) { self(self,left[u],u); siz[u]siz[left[u]]; } if(right[u]) { self(self,right[u],u); siz[u]siz[right[u]]; } vectorZtmp(k1); tmp[0]1; for(int i1;ik;i) { for(int x0,yi;xi;x,y--) { tmp[i]dp[left[u]][x]*dp[right[u]][y]; } } int rowa[u]-a[fa]; int colsiz[u]; dp[u][0]1; for(int i1;ik;i) { for(int x0,yi;xixcol;x,y--) { dp[u][i]tmp[x]*calc(row,col-x,y); } } }; dfs(dfs,root,0); coutdp[root][k]endl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }首先如果要将 k 个数填入 k*k 的区域方案数就是 k!。扩展一下若要想 k 个数填入 n*m 的区域方案数就是 C(n,k)*C(m,k)*k!即先从 n 行选 k 行再从 m 行选 k 行然后具体数的方案数是 k!。之后对数组建立小根堆组织的笛卡尔树然后根据树的结构划分每个节点负责的范围。对于当前节点 u若其父亲节点为 fa那么其负责的高度就是自己高度减去父亲高度负责的列数就是 u 的子树大小。原因是由于维护的小根堆那么从顶到底高度必然满足从低到高所以自然可以依次划分。而同样因为小根堆所以当前节点子树内的高度都是大于自己的又因为下标满足二叉搜索树那么子树内在列上肯定也是连续的所以列的长度必然就是子树大小。之后还是去笛卡尔树上 dp那么就是定义 dp[u][i] 为将 i 个数放到 u 这棵子树负责的区域的方案数初始 dp[0][0] 啥也不放有一种注意是整个子树而非只是当前区域。那么首先 dp[u][0] 不放数肯定有 1 种之后对于当前放的个数 i就是讨论在当前节点放 x 个在之前区域放 y 个使得 xyi 的方案。那么由于之前有了 n*m 区域放 k 个数的方案数这个就可以快速计算了。注意若之前区域放了数的话需要在列上减去放的个数因为已经被占用了。那么就只需要先计算左右孩子合并得到的之前区域方案数再和当前节点合并即可。5.B - Removing Blocks感觉在这种堆方块问题上笛卡尔树能很好的维护位置和高度或时间的有序关系。#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题注意特判 *不要红温不要急躁耐心一点 *WA了不要立马觉得是思路不对先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; templateclass T constexpr T power(T a, ll b) { T res 1; for (; b ! 0; b / 2, a * a) { if (b 1) { res * a; } } return res; } templateint M struct ModInt { public: constexpr ModInt() : x(0) {} templatetypename T constexpr ModInt(T x_) { T v x_ % M; if (v 0) { v M; } x v; } constexpr int val() const { return x; } constexpr ModInt operator() { x; if (x M) { x 0; } return *this; } constexpr ModInt operator(int) { ModInt res *this; (*this); return res; } constexpr ModInt operator--() { if (x 0) { x M - 1; } else { x--; } return *this; } constexpr ModInt operator--(int) { ModInt res *this; --(*this); return res; } constexpr ModInt operator-() const { ModInt res; res.x (x 0 ? 0 : M - x); return res; } constexpr ModInt inv() const { return power(*this, M - 2); } constexpr ModInt operator*(const ModInt rhs) { x ll(x) * rhs.val() % M; return *this; } constexpr ModInt operator(const ModInt rhs) { x rhs.val(); if (x M) { x - M; } return *this; } constexpr ModInt operator-(const ModInt rhs) { x - rhs.val(); if (x 0) { x M; } return *this; } constexpr ModInt operator/(const ModInt rhs) { return *this * rhs.inv(); } friend constexpr ModInt operator*(ModInt lhs, const ModInt rhs) { lhs * rhs; return lhs; } friend constexpr ModInt operator(ModInt lhs, const ModInt rhs) { lhs rhs; return lhs; } friend constexpr ModInt operator-(ModInt lhs, const ModInt rhs) { lhs - rhs; return lhs; } friend constexpr ModInt operator/(ModInt lhs, const ModInt rhs) { lhs / rhs; return lhs; } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator!(ModInt lhs, const ModInt rhs) { return lhs.val() ! rhs.val(); } friend constexpr std::istream operator(std::istream is, ModInt a) { ll i; is i; a i; return is; } friend constexpr std::ostream operator(std::ostream os, const ModInt a) { return os a.val(); } private: int x; }; templateint M, typename T ModIntM struct Comb { vectorT fac; vectorT inv; Comb(int n) { fac.assign(n, 1); for(int i1;in;i) { fac[i]fac[i-1]*i; } inv.assign(n, 1); inv[n-1]fac[n-1].inv(); for(int in-2;i0;i--) { inv[i]inv[i1]*(i1); } } templatestd::signed_integral U T P(U n, U m) { if(nm) { return 0; } return fac[n] * inv[n - m]; } templatestd::signed_integral U T C(U n, U m) { if(nm||m0) { return 0; } return fac[n] * inv[n - m] * inv[m]; } }; //power函数切记强转成 Z !!!!! constexpr int M 1e97; using Z ModIntM; constexpr int N 2e55; CombMcomb(N); templatestd::signed_integral U Z P(U n, U m) { return comb.P(n, m); } templatestd::signed_integral U Z C(U n, U m) { return comb.C(n, m); } void solve() { int n; cinn; vectorinta(n1); for(int i1;in;i) { cina[i]; } vectorZf(n1); for(int i1;in;i) { f[i]f[i-1](Z)1/i; } Z ans0; for(int i1;in;i) { ans(f[i]-1f[n-i1]-11)*a[i]; } ans*comb.fac[n]; coutansendl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }首先对于某一种删除顺序考虑建立下标为二叉搜索树删除时间为小根堆的笛卡尔树注意这里不以高度为小根堆了。那么建完可以发现对于每个位置其贡献的次数就是其在树上的高度因为只有当其祖先节点删除时才会贡献一次。那么对于所有 n! 种删除方案的总贡献如果能求出每种方案的期望贡献乘一下就是答案了。首先对于当前节点 u其高度期望就是其祖先节点数的期望再加一。那么又因为期望就是所有概率的累加那么 u 的期望就是其他 n-1 个点是 u 祖先的概率的累加。那么若要求 x 是 u 的祖先那么首先就要满足 x 在 u 之前删除。在这个基础上由于下标满足二叉搜索树的性质那么就要求 x 到 u 之间的所有节点都在 x 之后删除因为如果中间有个节点更早那么 x 和 u 就会被分开。那么如果要求 x 在 u 前面删除的概率首先总概率就是任意排列。但此时为了方便解决考虑不用 n! 处理。那么首先 x 到 u 这 x-u1 个数随意排列的方案数是 (x-u1)!之后再乘上其他数随意排列往里插的方案数。之后对于分子那么如果要让 x 在 u 前面就是在固定 x 之后剩下 x-u 个数在后面随意排列方案数就是 (x-u)!再乘上其他书随意排列往里插的方案数。此时就可以发现分子分母的后者可以消掉前者也可以消掉所以概率就是。那么预处理一下分数的累加和每次 O(1) 计算即可。这个转化成期望计算也太逆天了……总结努力努力再努力END

数据结构与算法：有序表（四）：笛卡尔树与 Treap

相关推荐

可信数据空间——可信数据空间AI大模型服务平台建设方案

Agent Harness的11大核心组件与工程实践（附下载）

尘封多年的老MD机还能再战十年？用Platinum-MD轻松搞定NetMD无损音频传输

更多资讯

烽火交换机带外登录、VLAN/PVID与IPTV组播配置实战

用Python+SQLite搭建路由器默认密码查询库与调试流程

旅游区景点管理系统课设：数据结构选型与最短路径算法实战

IIS 部署 .NET WebApi 全流程：从角色安装到端口放行

操作系统期末高分攻略：进程、调度、内存与文件系统核心考点精讲

Nemea 高速网络流量分析：从抓包瓶颈到流式异常检测架构

今日更新

MATLAB缩进快捷键与批量格式化实战指南

用Poco实现Qt风格信号与槽的跨平台C++方案

ESXi裸机虚拟化安装指南：从硬件兼容到虚拟机部署

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？