笛卡尔树
简介
笛卡尔树是一种平衡树，它的结构和treap相同，但是由于它能在O(n)时间构造，同时具有一些很有意思的性质。
构造
笛卡尔树的节点由键值对 \((k,w)\) 组成。其中键值 \(k\) 满足二叉搜索树性质，而键值 \(w\) 满足小根堆性质。
一个有趣的事实是，如果笛卡尔树的 \((k,w)\) 键值确定，且 \(k\) 互不相同 ，\(w\) 互不相同，那么这个笛卡尔树的结构是唯一的。
构建笛卡尔树需要用到栈，其步骤如下:
1.首先，将节点按照 \(k\) 值排序，保证树具有BST性质；
2.然后一个个插入，由于BST性质，我们只能插入到右链的末端；
3.将我们插入的节点 \(u\) 向上跳，直到找到一个w比它小的节点\(v\)，然后使\(u\)成为\(v\)的右儿子；
4.对于\(v\)本身的右子树，则成为\(u\)的左子树，由于\(v\)的右儿子的\(w\)一定大于\(w_u\)因此堆性质得以保证；
我们的栈维护的是笛卡尔树的右链，由于每个元素在栈中停留的时间是一个连续的区间，所以可以用栈维护，而这个栈显然在\((k,w)\)的视角都是单调的。
1.单纯实现一个最小堆，我们使用栈作为辅助空间来构造堆.当一个数组元素要构造节点时,他可以成为右链元素的子节点(比右链元素大),或者成为右链元素的父节点(比栈顶元素小)
2.还要将最小堆变成二叉搜索树。一个已入栈元素的下标<后入栈元素的下标,所以在第一步中,变成子节点的元素必须要成为右节点;变成父节点的元素,栈中的元素必须成为他的左子树,这样才保持了基于下标的二叉搜索树性质——\(votrubac\)
代码实现:
for(int i=1;i<=n;i++){
int k=top;
while(k>0&&w[s[k]]>w[i])k--;
if(k)r[s[k]]=i;//如果u是堆顶，那就不需要成为任何壬的儿砸
if(k<top)l[i]=s[k+1];//如果刚开始爬就被截停了，那他也没有儿砸了
s[++k]=i;
top=k;
}
以点 u 为根的子树是一段连续极长区间，\(w_u\) 是区间的最小值，区间在保证最小值不变的情况下不能再向两边延长。区间 [a,b]的最小值为 \(w[lca(a,b)]\)
例题
Removing Blocks
有 \(N\) 块砖块排列成一行，从左到右编号为 \(1\) 到 \(N\) 。每一个砖块都有一个重量，砖块 \(i\) 的重量为 \(A_i\)。 Snuke 会对这些 \(N\) 个砖块执行如下操作：
- 选择一个还没有被移除的砖块，然后移除它。这个操作的代价是与被移除的砖块相邻的砖块（包括它自己）的重量之和。我们定义两块砖 \(x\) 和 \(y ~(x \leq y)\) 是相邻的，当且仅当对于所有 \(z (x \leq z \leq y)\) ，砖块 \(z\) 仍然没有被移除。
有 \(N!\) 种移除砖块的可能顺序。你需要对于所有可能的顺序计算出移除完所有 \(N\) 块砖块的代价，并计算这些代价的和。由于答案可能非常大，答案需要对 \(10^9+7\) 取模。
考虑以\((数组下标，删除时间)\)构建键值对，以删除时间为 \(w\) ,设点权为\(a_i\).
则一个元素子树内的权值和就是删去它的贡献，设每个元素深为\(h_i\)，则有总代价为
\[\sum_{i=1}^{n}h_i\times a_i \]再考虑对于一个 \(j\) , \(i\) 是它祖先的充分必要条件是 \(j⋯i-1\)在\(i\)之前被删去，这个事件的期望是
\[\frac{(i-j)!}{(i-j+1)}= \frac1{i-j+1} \]所以\(E(h_i)\)为
\[\sum_{x=1}^{i-1}\frac{1}{i-x+1}+\sum_{i-1}^{n}\frac{1}{x-i+1}+1 \]所以答案为
\[n!\times\large\sum_{i=1}^{n}( \sum_{x=1}^{i-1}\frac{1}{i-x+1}+\sum_{i-1}^{n}\frac{1}{x-i+1}+1\large)\times a_i \]由于中间那一坨可以预处理，所以总时间复杂度O(n);
代码实现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,mod=1e9+7;
int fac[N],inv[N],s[N];
int n,a[N],ans;
signed main(){
cin>>n;
fac[0]=fac[1]=1;inv[0]=inv[1]=1;
for(int i=2;i<=100000;i++)fac[i]=fac[i-1]*i%mod;
for(int i=2;i<=100000;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;//线性求逆元
for(int i=1;i<=100000;i++)s[i]=(s[i-1]+inv[i])%mod;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)ans=(ans+(s[i]+s[n-i+1]-1)*a[i])%mod;
cout<<ans*fac[n]%mod;
}
标签：cartesian,笛卡尔,int,sum,移除,tree,键值,砖块 From： https://www.cnblogs.com/Hushizhi/p/17204602.html模意义下的逆元和实数意义下的逆元是同余的——hzm