首页 > 其他分享 >笛卡尔树学习笔记

笛卡尔树学习笔记

时间：2024-03-07 21:34:11浏览次数：25  
标签：ch 笛卡尔 int top 笔记 学习 序列 节点

笛卡尔树学习笔记

定义

笛卡尔树是一棵特殊的二叉树，它的每个节点都包含了两个值 \((k,w)\)。其中，整棵树关于 \(k\) 为一棵二叉搜索树，而关于 \(w\) 为一个小根堆（或大根堆）。

到这里可以发现，Treap 是一种特殊的笛卡尔树，因为 Treap 相当于给定了 \(k\)，而我们人为将其随机了一个 \(w\)。

性质

  1. 对于一棵笛卡尔树，它的中序遍历就是原先输入的序列 \(a\)。
    • 在插入序列 \(a\) 时，我们默认它的下标为 \(k\)。因此，原序列 \(a\) 中在某个数左边的数在笛卡尔树中也一定在这个数的左子树中，在某个数右边的数在笛卡尔树中也一定在这个数的右子树中。
  2. 在原序列中的区间 \([l,r]\) 的最小值，就是这个序列的笛卡尔树上 \(l\) 和 \(r\) 的最近公共祖先。
    • 因为 \(l\) 和 \(r\) 的公共祖先一定在区间 \([l,r]\) 中，并且在整个区间中深度最小。因为笛卡尔树关于 \(w\) 是小根堆，所以 \(l\) 和 \(r\) 的最近公共祖先是原序列中区间 \([l,r]\) 的最小值。
  3. 对于一个序列 \(a\)，如果它的 \(k,w\) 均互不重复，那么它建立出来的笛卡尔树是唯一的。
    • 因为 \(k\) 互不重复，所以能构建出唯一无根二叉搜索树。而因为笛卡尔树关于 \(w\) 是小根堆，所以 \(w\) 最小的节点为根。又因为 \(w\) 互不重复，所以根节点确定，所以笛卡尔树确定。

建树

建树要求知道所有数字的插入顺序和具体的值，缺一不可。通常按照 \(k\) 升序输入。

通过洛谷【P5854 【模板】笛卡尔树】来了解最优的建树方法。

  1. 通过性质 \(2\)，我们可以通过 ST 表找出一个区间的最小值，让它作为根节点，接着递归处理它的左子树和右子树。时间复杂度是 \(O(n\log n+n)\) 的，显然无法通过。
  2. 考虑到每一次插入要求关于 \(k\) 为一棵二叉搜索树，那么 \(k\) 大的值（即最后插入的值）一定在整个序列的最右边。因此通过单调栈维护整棵树的最右链，当栈顶节点的 \(w\) 值比当前节点大，就将其放在当前节点的左子树，反之直接将当前节点插入到栈顶节点的右子树中。时间复杂度是 \(O(n)\) 的。

code

void insert(int k,int w){
	while(top&&w<a[stk[top]])ls[k]=stk[top--];
	rs[stk[top]]=k;//最后的根节点就是 rs[0]
	stk[++top]=k;
	return ;
}

例题

洛谷【P5854 【模板】笛卡尔树】

Solution1【自己想的】

建立笛卡尔树，保存左右子树的编号，根据要求统计即可。另外一提，这道题卡常，需要加快读。

code1

#include <bits/stdc++.h>
using namespace std;

const int N=1e7;
int n,x,top;
int stk[N+5],ls[N+5],rs[N+5],a[N+5];
long long AnsL,AnsR;

int read(){
    int ret=0,ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ret=ret*10+ch-'0',ch=getchar();
    return ret;
}

void insert(int k,int w){
	while(top&&w<a[stk[top]])ls[k]=stk[top--];
	if(top)rs[stk[top]]=k;
	stk[++top]=k;
	return ;
}

int main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		insert(i,a[i]);
	}
	for(int i=1;i<=n;i++){
		AnsL^=(long long)i*(ls[i]+1);
		AnsR^=(long long)i*(rs[i]+1);
	}
	printf("%lld %lld",AnsL,AnsR);
    return 0;
}

洛谷【P1377 [TJOI2011] 树的序】

Solution1【自己想的】

考虑到题目中给出的输入相当于确定了 \(k\)，而下标则相当于 \(w\)。因为建立笛卡尔树需要按照 \(k\) 从小到大排序，因此首先排序，然后建立笛卡尔树，这个笛卡尔树就是对应的二叉搜索树。因为在父亲节点走到之前无法走到儿子节点，并且左儿子小于右儿子，所以这棵树的先序遍历就是要求的答案序列。

code1

#include <bits/stdc++.h>
using namespace std;

const int N=1e5;
int n,top,rt;
int stk[N+5],ls[N+5],rs[N+5];
pair<int,int>a[N+5];

int read(){
    int ret=0,ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ret=ret*10+ch-'0',ch=getchar();
    return ret;
}

void insert(int k,int w){
	while(top&&w<a[stk[top]].second)ls[k]=stk[top--];
	if(top)rs[stk[top]]=k;
	stk[++top]=k;
	return ;
}

void show(int x){
	printf("%d ",a[x].first);
	if(ls[x])show(ls[x]);
	if(rs[x])show(rs[x]);
	return ;
}

int main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=make_pair(read(),i);
	rt=a[1].first;
	sort(a,a+n+1);
	for(int i=1;i<=n;i++)insert(a[i].first,a[i].second);
	show(rt);
	return 0;
}

P2244. [hdu6305]RMQ Similar Sequence

Solution1【颓题解的】

因为序列 \(A,B\) 的所有子区间的 RMQ 相同，那么序列 \(A,B\) 的笛卡尔树应该是同构的。又因为序列 \(B\) 中的元素都是区间 \([0,1]\) 内的实数，所以序列 \(B\) 内有重复元素的概率无限趋近于 \(0\)。我们假设序列 \(B\) 中没有重复元素，那么根据性质 \(3\)，序列 \(B\) 的笛卡尔树应该是唯一的。接着考虑对于每一个序列 \(B\) 的笛卡尔树与序列 \(A\) 的笛卡尔树同构的概率。因为数字从左往右的顺序不变，根据性质 \(1\)，只要确定了根节点，那么两边的元素集合一定相等，所以只要所有子树的根节点都相同，那么两个笛卡尔树就是同构的。设以 \(i\) 为根节点的子树大小为 \(siz_i\)，那么笛卡尔树同构的概率为 \(\frac{1}{\prod_{i=1}^n siz_i}\)。而序列 \(B\) 内每一个元素的期望都是 \(\frac{1}{2}\)，所以符合条件序列 \(B\) 的权值期望为 \(\frac{n}{2}\)，所以序列 \(B\) 的权值期望为 \(\frac{n}{2\prod_{i=1}^nsiz_i}\)。

code1

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N=1e6,M=1e9+7;
int T,n,top,rt;
int a[N+5],stk[N+5],ls[N+5],rs[N+5],siz[N+5];

void insert(int k,int w){
	while(top&&w>a[stk[top]])ls[k]=stk[top--];
	if(top)rs[stk[top]]=k;
	else rt=k;
	stk[++top]=k;
	return ;
}

void dfs(int x){
	siz[x]=1;
	if(ls[x])dfs(ls[x]);
	if(rs[x])dfs(rs[x]);
	siz[x]+=siz[ls[x]]+siz[rs[x]];
	return ;
}

ll QuickPow(ll a,int b){
	ll res=1;
	while(b){
		if(b&1)res=res*a%M;
		a=a*a%M;
		b>>=1;
	}
	return res;
}

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		top=0;
		for(int i=1;i<=n;i++)ls[i]=rs[i]=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			insert(i,a[i]);
		}
		dfs(rt);
		long long sum=2;
		for(int i=1;i<=n;i++)sum=sum*siz[i]%M;
		printf("%lld\n",n*QuickPow(sum,M-2)%M);
	}
	return 0;
}

P2245. [SPOJ#2616]PERIODNI

Solution1【自己想的】

考虑到如果有一个最小的棋盘将两边分隔开，那么除去这个棋所在的行以外，剩下的两组棋盘互不干扰。即对于 \(i>h_x\)，棋盘 \(x\) 左边的第 \(i\) 行和棋盘 \(x\) 右边的第 \(i\) 行互不干扰。那么可以通过这一点进行树形 dp。我们发现，一个子树的根节点是整个区间的最小值，所以整棵树是一棵笛卡尔树。给出的高度相当于 \(w\)，下标相当于 \(k\)。接着令 \(f_{i,j}\) 表示节点 \(i\) 为根的子树中放置 \(j\) 个节点，且所有棋子所在行的编号不小于节点 \(i\) 的父亲节点的高度，即棋子的行编号在区间 \((h_{fa_x},+\infty)\) 内的方案数。

先考虑棋子编号在区间 \((h_x,+\infty)\) 的方案数，此时相当于一个背包，转移方程为：

\[f_{i,j}=\sum_{to\in son_i}\sum_{k=1}^{j}f_{to,k}\times f_{i,j-k} \]

注意此时为了不让数组刚更新的内容去更新其他内容，因此 \(j\) 应从大到小循环。接着考虑行编号在区间 \((h_{fa_x},h_x]\) 中的棋子。我们如果放 \(k\) 个这样的棋子，那么说明必须有一些列是空的，接着从范围内选出 \(k\) 个不同的数字然后分在这些空列当中，转移方程为：

\[f_{i,j}=\sum_{k=1}^{j}f_{i,j-k}\times C_{h_x-h_{fa_x}}^{k}\times A_{siz_i-(j-k)}^{k} \]

注意此时为了不让数组刚更新的内容去更新其他内容，因此 \(j\) 应从大到小循环。最后两个区间的方案数累加起来就是对应的值。最后的答案是 \(f_{rt,k}\)。

code1

#include <bits/stdc++.h>
using namespace std;

const int N=500,M=1e9+7,H=1e6;
int n,k,top,rt;
int stk[N+5],ls[N+5],rs[N+5],a[N+5],siz[N+5];
long long dp[N+5][N+5],f[H+5],g[H+5];

void insert(int k,int w){
	while(top&&w<a[stk[top]])ls[k]=stk[top--];
	rs[stk[top]]=k;
	stk[++top]=k;
	return ;
}

long long QuickPow(long long a,int b){
	long long res=1;
	while(b){
		if(b&1)res=res*a%M;
		a=a*a%M;
		b>>=1;
	}
	return res;
}

void pre(int N){
	f[0]=1;
	for(int i=1;i<=N;i++)f[i]=f[i-1]*i%M;
	g[N]=QuickPow(f[N],M-2);
	for(int i=N-1;i>=0;i--)g[i]=g[i+1]*(i+1)%M;
	return ;
}

long long C(int n,int m){
	if(n<m||n<0||m<0)return 0;
	return f[n]*g[n-m]%M*g[m]%M;
}

long long A(int n,int m){
	if(n<m||n<0||m<0)return 0;
	return f[n]*g[n-m]%M;
}

void dfs(int x,int lst){
	siz[x]=1;
	if(ls[x])dfs(ls[x],x);
	if(rs[x])dfs(rs[x],x);
	siz[x]+=siz[ls[x]]+siz[rs[x]];
	dp[x][0]=1;
	for(int i=k;i>=1;i--){
		for(int j=1;j<=min(i,siz[ls[x]]);j++)dp[x][i]=(dp[x][i]+dp[x][i-j]*dp[ls[x]][j]%M)%M;
	}
	for(int i=k;i>=1;i--){
		for(int j=1;j<=min(i,siz[rs[x]]);j++)dp[x][i]=(dp[x][i]+dp[x][i-j]*dp[rs[x]][j]%M)%M;
	}
	for(int i=min(k,siz[x]);i>=1;i--){
		for(int j=min(i,a[x]-a[lst]);j>=1;j--)dp[x][i]=(dp[x][i]+dp[x][i-j]*C(a[x]-a[lst],j)%M*A(siz[x]-i+j,j)%M)%M;
	}
	return ;
}

int main(){
	pre(H);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		insert(i,a[i]);
	}
	dfs(rs[0],0);
	printf("%lld",dp[rs[0]][k]);
	return 0;
}

P2246. [hdu4125]Moles

Solution1【自己想的】

问题即要求建一棵二叉搜索树、求解路径节点和模式串匹配。建立二叉搜索树可以和【洛谷【P1377 [TJOI2011] 树的序】】一样，按 \(k\) 值排序后，用笛卡尔树 \(O(n)\) 解决。路径上的节点只需要先走左子树，再走右子树得到欧拉序即可，dfs 是 \(O(n)\) 的。模式串匹配用 KMP，因为欧拉序最多 \(2n\) 个节点，所以也是 \(O(n)\) 的，所以时间复杂度 \(O(n)\)。

code1

#include <bits/stdc++.h>
using namespace std;

const int N=6e5,S=7e3;
int T,n,top,rt,tot1,tot2,cnt;
int t[N+5],stk[N+5],ls[N+5],rs[N+5],a[N+5],nxt[N+5];
char s1[(N<<1)+5],s2[S+5];

void insert(int k,int w){
	while(top&&w<t[stk[top]])ls[k]=stk[top--];
	if(top)rs[stk[top]]=k;
	else rt=k;
	stk[++top]=k;
	return ;
}

void dfs(int x){
	s1[tot1++]=x%2+'0';
	if(ls[x]){
		dfs(ls[x]);
		s1[tot1++]=x%2+'0';
	}
	if(rs[x]){
		dfs(rs[x]);
		s1[tot1++]=x%2+'0';
	}
	return ;
}

int main(){
	scanf("%d",&T);
	for(int c=1;c<=T;c++){
		scanf("%d",&n);
		top=tot1=cnt=0;
		for(int i=1;i<=n;i++)t[i]=ls[i]=rs[i]=nxt[i]=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			t[a[i]]=i;
		}
		for(int i=1;i<=n;i++)insert(i,t[i]);
		dfs(rt);
		scanf("%s",s2);
		tot2=strlen(s2);
		for(int i=0;s2[i];i++)nxt[i]=0;
		for(int i=1,j=0;i<tot2;i++){
			while(j&&s2[i]!=s2[j])j=nxt[j-1];
			if(s2[i]==s2[j])j++;
			nxt[i]=j;
		}
		for(int i=0,j=0;i<tot1;i++){
			while(j&&s1[i]!=s2[j])j=nxt[j-1];
			if(s1[i]==s2[j])j++;
			if(j==tot2){
				cnt++;
				j=nxt[j-1];
			}
		}
		printf("Case #%d: %d\n",c,cnt);
	}
	return 0;
}

P2247. [hdu6854]Kcats

Solution1【颓题解的】

考虑到 \(a_i\) 本质上是最后的笛卡尔树上，第 \(i\) 个节点的所有祖先中 \(k\) 值比自己小的节点的数量。接着考虑区间 dp，令 \(f_{i,j,d}\) 表示区间 \([l,r]\) 所对应的笛卡尔树的根节点的祖先中有 \(d\) 个 \(k\) 值比自己小。那么它的左儿子节点，即区间 \([l,rt]\) 的根节点的有贡献的祖先节点一定和它的祖先节点是一样的。但是它的右儿子节点，即区间 \((rt,r]\) 的根节点不仅有它有的祖先节点，还包含它本身。因为笛卡尔树满足小根堆，所以它的左子树一定比他大且按顺序排列，因此数字的组合可能为 \(C_{j-i}^{k-i}\)。转移方程为：

\[f_{i,j,d}=\sum_{k=i}^{j}\left\{\begin{matrix} \sum_{d=a_k}f_{i,k-1,d}\times f_{k+1,j,d+1}\times C_{j-i}^{k-i}(a_k\ne-1)\\ \sum_{d=1}^{n}f_{i,k-1,d}\times f_{k+1,j,d+1}\times C_{j-1}^{k-i}(a_k=-1) \end{matrix}\right. \]

code1

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N=100,M=1e9+7;
int t,n,l,r;
int a[N+5];
ll f[N+5],g[N+5],dp[N+5][N+5][N+5];

ll QuickPow(ll a,int b){
	ll res=1;
	while(b){
		if(b&1)res=res*a%M;
		a=a*a%M;
		b>>=1;
	}
	return res;
}

void pre(int N){
	f[0]=1;
	for(int i=1;i<=N;i++)f[i]=f[i-1]*i%M;
	g[N]=QuickPow(f[N],M-2);
	for(int i=N-1;i>=0;i--)g[i]=g[i+1]*(i+1)%M;
	return ;
}

ll C(int n,int m){
	if(n<m||n<0||m<0)return 0;
	return f[n]*g[n-m]%M*g[m]%M;
}

int main(){
	pre(N);
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				for(int k=1;k<=n;k++)dp[i][j][k]=0;
			}
		}
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=n;i>=1;i--){
			for(int j=i;j<=n;j++){
				for(int k=i;k<=j;k++){
					if(a[k]==-1){
						l=1;
						r=n;
					}else l=r=a[k];
					for(int d=l;d<=r;d++)dp[i][j][d]=(dp[i][j][d]+(i<k?dp[i][k-1][d]:1)*(k<j?dp[k+1][j][d+1]:1)%M*C(j-i,k-i)%M)%M;
				}
			}
		}
		printf("%lld\n",dp[1][n][1]);
	}
	return 0;
}

标签：ch,笛卡尔,int,top,笔记,学习,序列,节点
From： https://www.cnblogs.com/DycBlog/p/18059807

相关文章

  • A星算法笔记
    A星算法笔记参考：https://blog.csdn.net/hitwhylz/article/details/23089415原理heuristic启发式F=G+HG:distancebetweenstartandcurrentnodeH:distancebetweengoalandcurrentnode//TOSEARCH&CHECKManhatan距离:基本数据结构1.全局数组：openlistclose......
  • java基础 韩顺平老师的 面向对象（基础） 自己记的部分笔记
    194，对象内存布局基本数据类型放在堆里面，字符串类型放在方法区。栈：一般存放基本数据类型（局部变量）堆：存放对象（Catcat，数组等）方法区：常量池（常量，比如字符串），类加载信息 196，属性注意细节1，属性可以是基本数据类型，也可以是引用类型（对象，数组）2，属性的定义语法同变量，示例：访问修饰符属......
  • Contrastive Learning 对比学习 | 何恺明大神的 SimSiam
    论文题目：ExploringSimpleSiameseRepresentationLearning，CVPR2021。pdf：https://arxiv.org/abs/2011.10566相关博客：知乎|无门槛级讲解对比学习中的自监督模型Simsiam（通俗易懂）知乎|对比学习（ContrastiveLearning）：研究进展精要（解释了为什么Simsiam会演变成这样）知......
  • 3/7学习进度
    大二学期第二周日报 第一天第二天第三天第四天第五天所花时间（包括上课） 190min≈3h≈4h  代码量（行） 75150行左右  0  博客量（篇） 1 1 1  了解到的知识点安装matlab，文件操作，安卓数据库操作复习 vue、axios......
  • Denoising Implicit Feedback for Recommendation论文阅读笔记
    Abstract​ 隐式反馈的普遍性使它们成为构建在线推荐系统的默认选择。虽然大量的隐式反馈缓解了数据的稀疏性问题，但缺点是它们在反映用户的实际满意度方面没有那么干净。例如，在电子商务中，很大一部分点击并不能转化为购买，许多购买最终会得到负面评论。因此，解释隐式反馈中不可避免......
  • mysql.h学习记录
    目录简介简介mysql.h是MySQLCAPI的主要头文件，它为C开发者提供了一套函数和定义，以与MySQL服务器交互。这些函数和定义使得开发者能够编写应用程序，实现与MySQL服务器的连接、执行查询、检索结果等操作。以下是一些常见的函数及其在mysql.h中的简要介绍：连接和关......
  • 旧时 科大部分物理笔记
    （怎么不见了这么多，后期纸制笔记未录入）有心力的角速度上的惯性离心势能势能（\(l\)为角动量）：\(E_p=-\dfrac{1}{2}mw^2r^2=\dfrac{l^2}{2mr^2}\)(由\(l=mrv_\theta\)和动能分量\(\dfrac{1}{2}mv_\theta^2\)得)有效势能（总势能）对位置求导为0的是平衡点，其中二阶导大于\(0\)的是......
  • 【学习笔记】 - 基础数据结构 ：Link-Cut Tree(进阶篇)
    前言LCT没题写可以去写树剖和一些线段树合并的题练手LCT的概念原本的树剖是对树进行剖分，剖分为重边和轻边LCT则是对于树分为虚边和实边，特殊的，LCT可以没有虚边(例：银河英雄传说v2)单独被包含在一个实链里的点称作孤立点在树剖中，我们使用线段树/树状数组来维护重链在Link-Cut......
  • Vue学习笔记39--创建Vue脚手架
    创建Vue脚手架1.Vue脚手架是Vue官方提供的标准开发工具(开发平台)2.脚手架最新版本4.x3.文档：https://cli.vuejs.org/zh/操作步骤：第一步：(仅第一次执行)：全局安装@vue/cli(commandlineinterface)注：安装钱建议先设置镜像==》npmconfigsetregisterhttps://registry.npm.taoba......
  • (笔记)Linux信号（signal) 机制和信号量（semaphore）机制的区别
     字面上相似，但是本质上存在巨大的差别！ 一、Linux信号（signal)机制signal，又简称为信号（软中断信号）用来通知进程发生了异步事件。原理：一个进程收到一个信号与处理器收到一个中断请求可以说是一样的。信号是进程间通信机制中唯一的异步通信机制，一个进程不必通过任何操作来......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99