差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:笛卡尔树 [2020/07/05 12:46]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:笛卡尔树 [2020/07/27 22:56] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:笛卡尔树被移动至2020-2021:teams:legal_string:jxm2001:笛卡尔树
@@ 行 3: / 行 3: @@
 ===== 算法简介 =====
-一种二叉树，主要用于解决有关序列 $\text{RMQ}$ 问题和一些矩阵维护问题，建树时间复杂度 $O(n)$。
+一种二叉树，主要用于解决有关序列 $\text{RMQ}$ 问题和直方图问题，建树时间复杂度 $O(n)$。
 ===== 算法思想 =====
@@ 行 12: / 行 12: @@
   - 笛卡尔树的点权符合堆性质
   - 任意区间的 $\text{RMQ}$ 操作可以转换为笛卡尔树上两端点的 $\text{LCA}$ 操作
+事实上，笛卡尔树可以对任意二元组进行建树，对第一关键字满足二叉搜索树性质，对第二关键字满足堆性质。
+从上面性质也可以看出，笛卡尔树实际上就是一棵特殊的 $\text{Treap}$。
 接下来考虑建树，事实上可以按顺序插入序列，每次插入时由于插入结点下标最大，所以只能不停跳右子树。
@@ 行 22: / 行 26: @@
 [[https://www.luogu.com.cn/problem/P5854|洛谷p5854]]
+<code cpp>
+const int MAXN=1e7+5,Inf=2e9;
+int Stack[MAXN],v[MAXN],ch[MAXN][2],root;
+void build(int n){//小根堆笛卡尔树
+	int top=0;
+	v[0]=-Inf;Stack[++top]=0;
+	_rep(i,1,n){
+		while(v[i]<v[Stack[top]])top--;
+		ch[i][0]=ch[Stack[top]][1];
+		ch[Stack[top]][1]=i;
+		Stack[++top]=i;
+	}
+	root=Stack[2];
+}
+</code>
+===== 算法练习 =====
+==== 习题一 ====
+[[https://www.luogu.com.cn/problem/SP3734|SP3734]]
+=== 题意 ===
+给定一个  $N$ 列的表格，每列的高度为 $a_i$ 且底部对齐。
+要求向表格中填入 $k$ 个相同的数，填写时要求不能有两个数在同一列，或在同一行且中间表格不间断。
+问在取模意义下有多少种填法。
+=== 题解 1 ===
+建立根据表格高度建立笛卡尔树，将表格划分分 $N$ 个矩形。
+设 $f(i,j)$ 表示在以结点 $i$ 为根结点的子树所代表的区域中填写 $j$ 个数的填法种数，$H$ 为结点代表矩阵高度，$\text{sz}$ 代表结点子树大小。
+$g(i,j)$ 表示在以结点 $i$ 为根结点的子树所代表的区域中填写 $j$ 个数且不在根结点代表的矩形填写数字的填法种数。
+先在考虑从某个结点所代表的矩阵中选取 $k$ 个结点的选法。
+易知从 $n\times m$ 的矩阵中选取 $k$ 个结点的总数为 $k!C_n^kC_m^k$，预处理 $k!$ 和 $k!$ 的逆即可快速求出。
+容易得出状态转移方程
+\begin{equation}H=H_u-H_{fa},\text{sz}_u=1+\text{sz}_{lson}+\text{sz}_{rson}\end{equation}
+\begin{equation}g(u,i)=\sum_{j=0}^i f(\text{lson},j)\times f(\text{rson},i-j)\end{equation}
+\begin{equation}f(u,i)=\sum_{j=0}^i g(u,j)\times (i-j)!C_H^{i-j}C_{\text{sz}_u-j}^{i-j}\end{equation}
+边界条件为 $f(0,0)=g(0,0)=1$，时间复杂度 $O(nk^2)$。
 <hidden 查看代码>
 <code cpp>
-const int MAXN=1e7+5;
+const int MAXN=505,MAXH=1e6+5,mod=1e9+7;
-int Stack[MAXN],v[MAXN],ch[MAXN][2];
+LL frac[MAXH],inv[MAXH];
+LL quick_pow(LL a,LL b,LL mod){
+	LL t=1;
+	while(b){
+		if(b&1)
+		t=t*a%mod;
+		a=a*a%mod;
+		b>>=1;
+	}
+	return t%mod;
+}
+void get_inv(){
+	frac[0]=1;
+	_for(i,1,MAXH)
+	frac[i]=frac[i-1]*i%mod;
+	inv[MAXH-1]=quick_pow(frac[MAXH-1],mod-2,mod);
+	for(int i=MAXH-2;i>=0;i--)
+	inv[i]=inv[i+1]*(i+1)%mod;
+}
+int C(int n,int m){return frac[n]*inv[m]%mod*inv[n-m]%mod;}
+int cal(int r,int c,int k){
+	if(r<k||c<k)
+	return 0;
+	return 1LL*C(r,k)*C(c,k)%mod*frac[k]%mod;
+}
+int Stack[MAXN],v[MAXN],ch[MAXN][2],root;
+void build(int n){
+	int top=0,last=0;
+	_rep(i,1,n){
+		while(top&&v[i]<v[Stack[top]])top--;
+		if(top)ch[Stack[top]][1]=i;
+		if(top<last)ch[i][0]=Stack[top+1];
+		Stack[++top]=i;
+		last=top;
+	}
+	root=Stack[1];
+}
+int sz[MAXN],n,k;
+LL f[MAXN][MAXN],g[MAXN][MAXN];
+void dfs(int pos,int fa){
+	if(!pos)
+	return;
+	dfs(ch[pos][0],pos);
+	dfs(ch[pos][1],pos);
+	sz[pos]=sz[ch[pos][0]]+sz[ch[pos][1]]+1;
+	_rep(i,0,k)
+	_rep(j,0,i)
+	g[pos][i]=(g[pos][i]+f[ch[pos][0]][j]*f[ch[pos][1]][i-j])%mod;
+	int H=v[pos]-v[fa];
+	_rep(i,0,k)
+	_rep(j,0,i){
+		if(!g[pos][j])
+		break;
+		f[pos][i]=(f[pos][i]+g[pos][j]*cal(H,sz[pos]-j,i-j))%mod;
+	}
+}
+int main()
+{
+	get_inv();
+	f[0][0]=g[0][0]=1;
+	n=read_int(),k=read_int();
+	_rep(i,1,n)
+	v[i]=read_int();
+	build(n);
+	dfs(root,0);
+	enter(f[root][k]);
+	return 0;
+}
+</code>
+</hidden>
+=== 题解 2 ===
+另外，还可以用笛卡尔树 $+$ 树上背包解决上述问题，常数较小，其中 $\text{dp}$ 数组第一次转移表示 $g$，第二次转移表示 $f$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=505,MAXH=1e6+5,mod=1e9+7;
+LL frac[MAXH],inv[MAXH];
+LL quick_pow(LL a,LL b,LL mod){
+	LL t=1;
+	while(b){
+		if(b&1)
+		t=t*a%mod;
+		a=a*a%mod;
+		b>>=1;
+	}
+	return t%mod;
+}
+void get_inv(){
+	frac[0]=1;
+	_for(i,1,MAXH)
+	frac[i]=frac[i-1]*i%mod;
+	inv[MAXH-1]=quick_pow(frac[MAXH-1],mod-2,mod);
+	for(int i=MAXH-2;i>=0;i--)
+	inv[i]=inv[i+1]*(i+1)%mod;
+}
+int C(int n,int m){return frac[n]*inv[m]%mod*inv[n-m]%mod;}
+int Stack[MAXN],v[MAXN],ch[MAXN][2],root;
 void build(int n){//小根堆的笛卡尔树
 	int top=0,last=0;
@@ 行 36: / 行 190: @@
 		last=top;
 	}
+	root=Stack[1];
+}
+int sz[MAXN],n,k;
+LL dp[MAXN][MAXN];
+void dfs(int pos,int fa){
+	if(!pos)
+	return;
+	dfs(ch[pos][0],pos);
+	dfs(ch[pos][1],pos);
+	sz[pos]=1,dp[pos][0]=1;
+	_for(dir,0,2){//计算从子树中选取i个结点的背包总数
+		if(!ch[pos][dir])continue;
+		sz[pos]+=sz[ch[pos][dir]];
+		for(int i=min(k,sz[pos]);i;i--)
+		_rep(j,1,min(sz[ch[pos][dir]],i))
+		dp[pos][i]=(dp[pos][i]+dp[pos][i-j]*dp[ch[pos][dir]][j])%mod;
+	}
+	int H=v[pos]-v[fa],Inf=min(k,sz[pos]);
+	for(int i=Inf-1;i>=0;i--)//计算从子树中选取i个结点，从当前矩阵中选取j个结点的贡献
+	_rep(j,1,min(Inf-i,H))
+	dp[pos][i+j]=(dp[pos][i+j]+dp[pos][i]*C(H,j)%mod*C(sz[pos]-i,j)%mod*frac[j]%mod)%mod;
+}
+int main()
+{
+	get_inv();
+	n=read_int(),k=read_int();
+	_rep(i,1,n)
+	v[i]=read_int();
+	build(n);
+	dfs(root,0);
+	enter(dp[root][k]);
+	return 0;
 }
 </code>
 </hidden>
-===== 算法练习 =====
+==== 习题二 ====
-[[https://www.luogu.com.cn/problem/SP3734|SP3734]]
+[[https://ac.nowcoder.com/acm/contest/5668/H|牛客暑期多校(第三场) H 题]]
+=== 题意 ===
+有一个长度为 $n$ 的字符串 $s_0$, 第 $i$ 个字符是数字 $i\bmod 10$。
+给定一个 $0\sim n-1$ 的排列 $p$ 和一个数值范围在 $0\sim 9$ 的数列 $d$。
+字符串 $s_i$ 是把字符串 $s_{i-1}$ 的第 $p_i$ 个字符改成 $d_i$ 的结果。
+将这 $n+1$ 个字符串按字典序排序，字典序相同时按字符串编号排序，输出每个字符串在排序后的位置(范围为 $0\sim n$)。
+=== 题解 ===
+首先假设所有 $d_i\neq p_i\bmod 10$，先考虑 $p_i=1$ 的位置。
+如果有 $d_i\lt p_i\bmod 10$，则显然有 $s_0\sim s_{i-1}$ 字典序大于 $s_i\sim s_n$，考虑将 $s_0\sim s_{i-1}$ 排名加上 $n-i+1$。
+如果有 $d_i\gt p_i\bmod 10$，则显然有 $s_0\sim s_{i-1}$ 字典序小于 $s_i\sim s_n$，考虑将 $s_i\sim s_n$ 排名加上 $i$。
+接下来 $p_i=1$ 将 $s$ 分为 $s_0\sim s_{i-1},s_i\sim s_n$ 两个区间，且两区间互不影响，可以分别递归求解。
+由于每次需要找到该区间 $p_i$ 最小的位置并划分区间，发现笛卡尔树恰好满足要求。
+排名修改可以考虑差分处理。
+最后是 $d_i=p_i\bmod 10$ 的情况，可以考虑将 $p_i$ 修改为 $\inf$，这样 $p_i$ 的影响一定会最后考虑。
-==== 题意 ====
+由于此时字典序相同，所以是 $s_\text{left}\sim s_{i-1}$ 字典序小于 $s_i\sim s_\text{right}$。
-==== 题解 ====
+该情况影响与 $d_i\gt p_i\bmod 10$ 的情况相同，考虑合并这两种情况，改为 $d_i\ge p_i\bmod 10$。
 <hidden 查看代码>
 <code cpp>
+const int MAXN=2e6+5,Inf=1e9,Base=1e7+19,Mod=1e9+7;
+int n,p[MAXN],d[MAXN];
+void init(){
+	int seed=read_int(),a=read_int(),b=read_int(),mod=read_int();
+	_for(i,0,n)p[i]=i;
+	_for(i,1,n){
+		swap(p[i],p[seed%(i+1)]);
+		seed=(1LL*seed*a+b)%mod;
+	}
+	seed=read_int(),a=read_int(),b=read_int(),mod=read_int();
+	_for(i,0,n){
+		d[i]=seed%10;
+		seed=(1LL*seed*a+b)%mod;
+	}
+	for(int i=n;i;i--)p[i]=p[i-1],d[i]=d[i-1];
+}
+int Stack[MAXN],ch[MAXN][2],root;
+void build(int n){
+	int top=0;
+	p[0]=-Inf;Stack[++top]=0;
+	_rep(i,1,n){
+		while(p[i]<p[Stack[top]])top--;
+		ch[i][0]=ch[Stack[top]][1];
+		ch[Stack[top]][1]=i;
+		Stack[++top]=i;
+	}
+	root=Stack[2];
+}
+int s[MAXN];
+void dfs(int pos,int lef,int rig){
+	if(lef>=rig)return;
+	if(d[pos]>=0){
+		s[pos]+=pos-lef;
+		s[rig+1]-=pos-lef;
+	}
+	else{
+		s[lef]+=rig-pos+1;
+		s[pos]-=rig-pos+1;
+	}
+	dfs(ch[pos][0],lef,pos-1);
+	dfs(ch[pos][1],pos,rig);
+}
+int main()
+{
+	int t=read_int();
+	while(t--){
+		n=read_int();
+		init();
+		s[0]=0;
+		_rep(i,1,n){
+			s[i]=0;
+			d[i]-=p[i]%10;
+			if(!d[i])p[i]=Inf;
+		}
+		build(n);
+		dfs(root,0,n);
+		_rep(i,1,n)
+		s[i]+=s[i-1];
+		int ans=0,base=1;
+		_rep(i,0,n){
+			ans=(ans+1LL*s[i]*base)%Mod;
+			base=1LL*base*Base%Mod;
+		}
+		enter(ans);
+	}
+	return 0;
+}
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具