Part 1:知识点
笛卡尔树是一种二叉树,每个节点有两个两个值 \((k,w)\)
其中 \(k\) 满足二叉搜索树的性质,\(w\) 满足二叉堆的性质
一些性质
-
任何子节点的 \(w\) 小于(或大于)父节点的 \(w\)
-
对于任何父节点,左节点的 \(k\) 小于父节点的 \(k\),右节点的 \(k\) 大于父节点的 \(k\)
-
若 \(k\) 值为数组下标,那么任意两个节点 \(u,v\) 的最近公共祖先就是区间 \([u,v]\) 的极值
笛卡尔树的构建
我们以 \(k\) 作为元素下标,\(w\) 作为元素权值,构建一个小根堆
每次插入一个节点 \(x\) 时,我们都只在右链插入。我们从根节点开始往下跳,找到第一个满足 \(w_y>w_x\) 的 \(y\),然后把 \(x\) 接在 \(fa[y]\) 的右边,把 \(y\) 接在 \(x\) 的左边
可以证明,这样插入是满足笛卡尔树的性质的
由于每个节点只会进出右链一次,所以时间复杂度 \(O(n)\)
Part 2:习题
建立一个单调栈去维护右链,这个栈单调递增
插入一个节点 \(x\) 时,若栈顶权值大于 \(w_x\) 就弹出
最后将 \(x\) 接在栈顶的右边,将最后一个出栈的元素接在 \(x\) 的左边,并将 \(x\) 入栈
不断重复即可,最后以 sta[1]
作为根节点
#include<bits/stdc++.h>
using namespace std;
const int N=10000010;
int n,a[N];
int sta[N],t,ch[N][2];
long long L,R;
int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0' || c>'9')
{
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0' && c<='9')
{
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
return x*f;
}
int main()
{
n=read();
for(int i=1; i<=n; i++)
a[i]=read();
sta[++t]=0;
for(int i=1; i<=n; i++)
{
while(t && a[sta[t]]>a[i])
ch[i][0]=sta[t--];
ch[sta[t]][1]=i;
sta[++t]=i;
}
for(int i=1; i<=n; i++)
{
L^=1LL*i*(ch[i][0]+1);
R^=1LL*i*(ch[i][1]+1);
}
printf("%lld %lld",L,R);
return 0;
}
P1377 [TJOI2011] 树的序
满足二叉搜索树性质的是键值 \(k\),满足堆性质的是插入的顺序
以此构建一棵笛卡尔树后输出中序遍历即可
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,a[N];
int sta[N],t,ch[N][2];
void dfs(int x)
{
if(x)
printf("%d ",x);
if(ch[x][0])
dfs(ch[x][0]);
if(ch[x][1])
dfs(ch[x][1]);
}
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
int x=0;
scanf("%d",&x);
a[x]=i;
}
sta[++t]=0;
for(int i=1; i<=n; i++)
{
while(t && a[sta[t]]>a[i])
ch[i][0]=sta[t--];
ch[sta[t]][1]=i;
sta[++t]=i;
}
dfs(sta[1]);
return 0;
}
\(n\) 个数,\(m\) 个询问区间最大值,询问随机,\(n,m\leq 2\times 10^7\)
不带修的 \(\rm RMQ\),显然 \(\rm ST\) 表不可以
利用笛卡尔树的性质三,我们可以将问题转化成求 \(m\) 次 \(\rm LCA\),可以使用 \(\rm Tarjan\)
但由于这题数据随机,所以我们直接从根节点暴力向下跳即可
#include<bits/stdc++.h>
using namespace std;
const int N=20000010;
int n,m,s,a[N];
int sta[N],t,ch[N][2];
unsigned long long ans;
namespace GenHelper
{
unsigned z1,z2,z3,z4,b;
unsigned rand_()
{
b=((z1<<6)^z1)>>13;
z1=((z1&4294967294U)<<18)^b;
b=((z2<<2)^z2)>>27;
z2=((z2&4294967288U)<<2)^b;
b=((z3<<13)^z3)>>21;
z3=((z3&4294967280U)<<7)^b;
b=((z4<<3)^z4)>>12;
z4=((z4&4294967168U)<<13)^b;
return (z1^z2^z3^z4);
}
}
void srand(unsigned x)
{
using namespace GenHelper;
z1=x;
z2=(~x)^0x233333333U;
z3=x^0x1234598766U;
z4=(~x)+51;
}
int read()
{
using namespace GenHelper;
int a=rand_()&32767;
int b=rand_()&32767;
return a*32768+b;
}
int query(int l,int r)
{
int cur=sta[1];
while(1)
{
if(l<=cur && cur<=r)
return a[cur];
if(cur<l)
cur=ch[cur][1];
else
cur=ch[cur][0];
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
srand(s);
for(int i=1; i<=n; i++)
a[i]=read();
sta[++t]=0;
for(int i=1; i<=n; i++)
{
while(t && a[sta[t]]<a[i])
ch[i][0]=sta[t--];
ch[sta[t]][1]=i;
sta[++t]=i;
}
for(int i=1; i<=m; i++)
{
int l=read()%n+1;
int r=read()%n+1;
if(l>r)
swap(l,r);
ans+=(unsigned long long)query(l,r);
}
printf("%llu",ans);
return 0;
}
P6453 [COCI2008-2009#4] PERIODNI
(双倍经验)
一道笛卡尔树的经典题目
以 \(h_i\) 为权值建立一颗小根线段树
这样做之后可以将原表格横向切割分成若干个矩形,当前矩形的长为 \(size[x]\),高为 \(h[x]-h[fa]\)。接下来我们就可以在笛卡尔树上进行树形 \(\rm dp\)
设 \(f[x][i]\) 表示在以 \(x\) 为根的子树内放 \(i\) 个数的方案数,则枚举左右子树(用 \(l,r\) 表示)放数的个数 \(j,t\),就有方程
\[f[x][i]=\sum_{j+t\leq i}f[l][j]\times f[r][t]\times \binom{size[x]-j-t}{i-j-t}\times\binom{h[x]-h[fa]}{i-j-t}\times (i-j-t)! \]后面的那坨组合数与阶乘相乘表示在当前节点表示的矩形当中放 \(i-j-t\) 个数的方案数。因为子树中放了 \(j+t\) 所以长度要减它们,阶乘表示选出的行和列的对应方案
注意到后面的式子只和 \(j+t\) 有关,所以将式子变换一下
\[f[x][i]=\sum_{s\leq i}{\binom{size[x]-s}{i-s}\times\binom{h[x]-h[fa]}{i-s}\times(i-s)!\:}\times \sum_{j+k=s}{f[l][j]\times f[r][k]} \]后面那坨式子可以 \(O(n^2)\) 预处理出来,所以总的时间复杂度 \(O(n^3)\)
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=510,M=1000010;
const LL MOD=1e9+7;
int n,k,a[N],ch[N][2],sta[N],t,size[N];
LL fac[M],inv[M],f[N][N],g[N][N];
LL ksm(int x,int y)
{
LL res=1;
while(y)
{
if(y&1)
res=(1LL*res*x)%MOD;
x=1LL*x*x%MOD;
y>>=1;
}
return res;
}
void prework()
{
fac[0]=inv[0]=1;
for(int i=1; i<=M-10; i++)
{
fac[i]=(fac[i-1]*i)%MOD;
inv[i]=ksm(fac[i],MOD-2);
}
}
LL C(int x,int y)
{
if(y>x)
return 0;
return fac[x]*inv[x-y]%MOD*inv[y]%MOD;
}
void dfs(int x,int fa)
{
if(ch[x][0])
dfs(ch[x][0],x);
if(ch[x][1])
dfs(ch[x][1],x);
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
int h=a[x]-a[fa];
LL tmp=0;
for(int i=0; i<=size[ch[x][0]]; i++)
for(int j=0; j<=size[ch[x][1]]; j++)
(g[x][i+j]+=f[ch[x][0]][i]*f[ch[x][1]][j]%MOD)%=MOD;
for(int i=0; i<=size[x]; i++)
for(int j=0; j<=size[x]-1; j++)
(f[x][i]+=g[x][j]*C(size[x]-j,i-j)%MOD*C(h,i-j)%MOD*fac[i-j]%MOD)%=MOD;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
sta[++t]=0;
for(int i=1; i<=n; i++)
{
while(t && a[sta[t]]>a[i])
ch[i][0]=sta[t--];
ch[sta[t]][1]=i;
sta[++t]=i;
}
prework();
f[0][0]=1;
dfs(sta[0],0);
printf("%lld",f[sta[1]][k]);
return 0;
}
标签:ch,sta,笛卡尔,int,times,节点
From: https://www.cnblogs.com/xishanmeigao/p/17612585.html