【學(xué)習(xí)筆記】笛卡爾樹
前言
本來早就該學(xué)笛卡爾樹了，但暑假打模擬賽就一直沒學(xué)成。于是就打算先不學(xué)了，結(jié)果又發(fā)現(xiàn)后面有個(gè)笛卡爾樹專題，只好來學(xué)學(xué)。
定義
笛卡爾樹是一棵二叉樹，每個(gè)點(diǎn)有一個(gè)鍵和一個(gè)值，鍵滿足堆的性質(zhì)，值滿足二叉搜索樹的性質(zhì)。沒錯(cuò)當(dāng)鍵隨機(jī)時(shí)，這就是個(gè) Treap。
建樹
如果值單調(diào)遞增，那么就可以線性建樹。具體地，維護(hù)整棵樹的右鏈。右鏈就是從根開始不停往右兒子走的鏈。因?yàn)橹颠f增所以新加的點(diǎn)一定會(huì)在右鏈中。假設(shè)新加入的點(diǎn) \(u\) 值為 \(k\) 鍵為 \(w\)，記為 \((k,w)\)，則從右鏈下端開始不斷向上比較，找到一個(gè) \(x\) 使它的鍵小于 \(w\)。那么 \(u\) 就成為 \(x\) 的右兒子，\(x\) 原本的右兒子就成為 \(u\) 的左兒子。
放張圖更直觀（紅色方框即為右鏈）：
圖中的數(shù)字就是相應(yīng)的點(diǎn)的鍵。顯然用單調(diào)棧來維護(hù)右鏈就行了。
核心代碼：
for(int i=1;i<=n;i++){
while(top&&a[zhan[top]]>a[i]){
top--;
}
int &tmp=top?rs[zhan[top]]:rt;
ls[i]=tmp;
tmp=i;
zhan[++top]=i;
}
代碼中值為 \(i=1\dots n\)，對(duì)應(yīng)的鍵為 \(a_i\)。
例題
[luogu5854]笛卡爾樹模板
按如上方式建樹即可。值得一提的是通過這道題可以發(fā)現(xiàn)：當(dāng)鍵與值都互不相同時(shí)，笛卡爾樹的形態(tài)是唯一的。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e7+5;
int n,a[maxn],rt;
int zhan[maxn],top;
int ls[maxn],rs[maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=1;i<=n;i++){
while(top&&a[zhan[top]]>a[i]){
top--;
}
int &tmp=top?rs[zhan[top]]:rt;
ls[i]=tmp;
tmp=i;
zhan[++top]=i;
}
ll ans1=0,ans2=0;
for(int i=1;i<=n;i++){
ans1^=i*1ll*(ls[i]+1);
ans2^=i*1ll*(rs[i]+1);
}
printf("%lld %lld",ans1,ans2);
return 0;
}
}
int main(){return asbt::main();}
[TJOI2011] 樹的序
觀察原樹的建樹方式，發(fā)現(xiàn)先加的一定在后加的上面。換句話說對(duì)于題中給出的 \(k_i\)，下標(biāo) \(i\) 為鍵而 \(k_i\) 為值。因此先將 \(k\) 排序，用笛卡爾樹的方式線性建樹。
然后我們要找到能建出相同樹的序列，必然也是從上向下建的，而我們又想要字典序最小，這還是一棵二叉搜索樹，因此必然要先輸出根，再遍歷左子樹，然后再遍歷右子樹。一個(gè) dfs 即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,a[maxn],p[maxn];
int rt,ls[maxn],rs[maxn];
int top,zhan[maxn];
il void dfs(int u){
if(!u){
return ;
}
printf("%d ",u);
dfs(ls[u]);
dfs(rs[u]);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
p[i]=i;
}
sort(p+1,p+n+1,[](const int &x,const int &y){return a[x]<a[y];});
for(int i=1;i<=n;i++){
// cout<<p[i]<<"\n";
while(top&&p[zhan[top]]>p[i]){
top--;
}
int &tmp=top?rs[zhan[top]]:rt;
ls[i]=tmp;
tmp=i;
zhan[++top]=i;
}
// for(int i=1;i<=n;i++){
// cout<<i<<" "<<ls[i]<<" "<<rs[i]<<"\n";
// }
dfs(rt);
return 0;
}
}
int main(){return asbt::main();}
[hdu6305]RMQ Similar Sequence
首先，對(duì) \(A\) 數(shù)組建一個(gè)滿足大根堆性質(zhì)的笛卡爾樹。
這時(shí)候你發(fā)現(xiàn)，\(RMQ(A,l,r)\) 就是 \(l\) 和 \(r\) 的 \(lca\)。
因此如果也類似地給 \(B\) 建出笛卡爾樹，這兩棵樹一定是相同的。因?yàn)?\(B\) 的和的期望是確定的，即 \(\frac{n}{2}\)，因此只需計(jì)算一個(gè)笛卡爾樹與 \(A\) 的笛卡爾樹相同的概率就行了。
顯然對(duì)于每棵子樹，只要根都是相同的，則樹就一定是相同的。設(shè) \(sz\) 為子樹大小，則概率為 \(\frac{1}{\prod{sz_i}}\)。因此答案為\(\frac{n}{2\prod{sz_i}}\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5,mod=1e9+7;
int T,n,a[maxn],rt;
int zhan[maxn],top;
int ls[maxn],rs[maxn];
int inv[maxn],sz[maxn];
il void dfs(int u){
// cout<<u<<"\n";
if(!u){
return ;
}
dfs(ls[u]);
dfs(rs[u]);
sz[u]=sz[ls[u]]+sz[rs[u]]+1;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
inv[1]=1;
for(int i=2;i<=1e6;i++){
inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;
}
// for(int i=1;i<=1e6;i++){
// cout<<i*1ll*inv[i]%mod<<"\n";
// }
read(T);
while(T--){
read(n);
top=rt=0;
for(int i=1;i<=n;i++){
read(a[i]);
while(top&&a[zhan[top]]<a[i]){
top--;
}
int &tmp=top?rs[zhan[top]]:rt;
ls[i]=tmp;
tmp=i;
zhan[++top]=i;
}
dfs(rt);
int ans=inv[2]*1ll*n%mod;
for(int i=1;i<=n;i++){
ans=ans*1ll*inv[sz[i]]%mod;
}
printf("%d\n",ans);
for(int i=1;i<=n;i++){
ls[i]=rs[i]=sz[i]=0;
}
}
return 0;
}
}
int main(){return asbt::main();}
[洛谷 P6453]PERIODNI
考慮如果 \(a_i\) 很小，那 \(i\) 兩邊的高于 \(a_i\) 的部分就成了兩個(gè)獨(dú)立的子問題。因此可以建立小根堆笛卡爾樹，然后進(jìn)行樹形 DP。
設(shè) \(f_{u,i}\) 表示 \(u\) 的子樹中高于 \(a_{fa_u}\) 的地方放了 \(i\) 個(gè)點(diǎn)的方案數(shù)。顯然答案為 \(f_{rt,m}\)。
考慮轉(zhuǎn)移。首先是高于 \(a_u\) 的部分，顯然可以通過樹上背包轉(zhuǎn)移：
然后是 \((a_{fa_u},a_u]\) 的部分。設(shè)要放 \(i\) 個(gè)，有 \(j\) 個(gè)在 \((a_{fa_u},a_u]\)，剩下大于 \(a_u\)，即要在剩下 \(sz_u-(i-j)\) 個(gè)節(jié)點(diǎn)、\(a_u-a_{fa_u}\) 個(gè)高度中選擇 \(j\) 個(gè)位置放點(diǎn)。于是有轉(zhuǎn)移方程：
注意兩次轉(zhuǎn)移中都是小的更新大的，所以 \(i\) 要倒序遍歷。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=505,mod=1e9+7,maxm=1e6+5;
int n,m,a[maxn],sz[maxn];
int rt,top,zhan[maxn];
int ls[maxn],rs[maxn];
int f[maxn][maxn];
int fac[maxm],inv[maxm];
il int qpow(int x,int y){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
x=x*1ll*x%mod,y>>=1;
}
return res;
}
il void init(int x){
fac[0]=1;
for(int i=1;i<=x;i++){
fac[i]=fac[i-1]*1ll*i%mod;
}
inv[x]=qpow(fac[x],mod-2);
for(int i=x;i;i--){
inv[i-1]=inv[i]*1ll*i%mod;
}
}
il int C(int x,int y){
if(x<y||y<0){
return 0;
}
return fac[x]*1ll*inv[y]%mod*inv[x-y]%mod;
}
il int A(int x,int y){
if(x<y||y<0){
return 0;
}
return fac[x]*1ll*inv[x-y]%mod;
}
il void dfs(int u,int fa){
if(!u){
return ;
}
dfs(ls[u],u),dfs(rs[u],u);
sz[u]=sz[ls[u]]+sz[rs[u]]+1;
f[u][0]=1;
for(int i=min(m,sz[u]);i;i--){
for(int j=1;j<=min(i,sz[ls[u]]);j++){
f[u][i]=(f[u][i]+f[u][i-j]*1ll*f[ls[u]][j])%mod;
}
}
for(int i=min(m,sz[u]);i;i--){
for(int j=1;j<=min(i,sz[rs[u]]);j++){
f[u][i]=(f[u][i]+f[u][i-j]*1ll*f[rs[u]][j])%mod;
}
}
for(int i=min(m,sz[u]);i;i--){
for(int j=1;j<=i;j++){
f[u][i]=(f[u][i]+f[u][i-j]*1ll*C(a[u]-a[fa],j)%mod*A(sz[u]-i+j,j))%mod;
}
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
for(int i=1;i<=n;i++){
read(a[i]);
while(top&&a[zhan[top]]>a[i]){
top--;
}
int &tmp=top?rs[zhan[top]]:rt;
ls[i]=tmp;
tmp=zhan[++top]=i;
}
init(1e6);
dfs(rt,0);
printf("%d",f[rt][m]);
return 0;
}
}
int main(){return asbt::main();}
[hdu4125]Moles
顯然我們找到原樹模 \(2\) 意義下的歐拉序，跑一個(gè) kmp 就好了。
考慮如何建樹，這棵樹按 \(a\) 值滿足二叉搜索樹的性質(zhì)，按下標(biāo)滿足小根堆的性質(zhì)。所以這就是一棵笛卡爾樹。線性建樹即可。時(shí)間復(fù)雜度 \(O(n\log n)\)。
Code
#include<cstdio>
#include<ctype.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=6e5+5;
int T,n,zhan[maxn],nxt[maxn];
int a[maxn],p[maxn],tot;
int ls[maxn],rs[maxn];
char s[maxn],t[maxn<<1];
il void dfs(int u){
t[++tot]=u&1|48;
if(ls[u]){
dfs(ls[u]);
t[++tot]=u&1|48;
}
if(rs[u]){
dfs(rs[u]);
t[++tot]=u&1|48;
}
}
il void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
p[i]=i;
}
scanf(" %s",s+1);
int len=strlen(s+1);
int top=0,rt=0;
sort(p+1,p+n+1,[](const int &x,const int &y){return a[x]<a[y];});
for(int i=1;i<=n;i++){
while(top&&p[zhan[top]]>p[i]){
top--;
}
int &tmp=top?rs[zhan[top]]:rt;
ls[i]=tmp;
tmp=zhan[++top]=i;
}
tot=0;
dfs(rt);
// for(int i=1;i<=tot;i++){
// cout<<t[i];
// }
// puts("");
nxt[1]=0;
for(int i=2,j=0;i<=len;i++){
while(j&&s[j+1]!=s[i]){
j=nxt[j];
}
if(s[j+1]==s[i]){
j++;
}
nxt[i]=j;
}
int ans=0;
for(int i=1,j=0;i<=tot;i++){
while(j&&s[j+1]!=t[i]){
j=nxt[j];
}
if(s[j+1]==t[i]){
j++;
}
if(j==len){
ans++,j=nxt[j];
}
}
printf("%d\n",ans);
for(int i=1;i<=n;i++){
ls[i]=rs[i]=0;
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
// cout<<cplx::usdmem();
read(T);
for(int i=1;i<=T;i++){
printf("Case #%d: ",i);
solve();
}
return 0;
}
}
int main(){return asbt::main();}
[hdu6854]Kcats
考慮 \(a\) 的實(shí)際含義，即為 \(p\) 的小根笛卡爾樹上 \(i\) 到根上權(quán)值 \(\le\) 的點(diǎn)數(shù)。于是可以進(jìn)行區(qū)間 dp。設(shè) \(f_{i,j,x}\) 表示 \([i,j]\) 的根的 \(a\) 值為 \(x\) 的方案數(shù)。于是有轉(zhuǎn)移：
時(shí)間復(fù)雜度是 \(O(Tn^4)\) 的，但是能過。
Code
#include<cstdio>
#include<iostream>
#include<functional>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
int main(){
ios::sync_with_stdio(0),cin.tie(0);
const int mod=1e9+7;
function<int(int,int)>qpow=[](int x,int y)->int{
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
y>>=1,x=x*1ll*x%mod;
}
return res;
};
int *fac=new int[105](),*inv=new int[105]();
fac[0]=1;
for(int i=1;i<=100;i++){
fac[i]=fac[i-1]*1ll*i%mod;
}
inv[100]=qpow(fac[100],mod-2);
for(int i=100;i;i--){
inv[i-1]=inv[i]*1ll*i%mod;
}
// for(int i=0;i<=100;i++){
// cout<<fac[i]<<" "<<fac[i]*1ll*inv[i]%mod<<"\n";
// }
function<int(int,int)>C=[=](int x,int y)->int{
if(x<y||y<0){
return 0;
}
return fac[x]*1ll*inv[y]%mod*inv[x-y]%mod;
};
int *a=new int[105]();
int (*f)[105][105]=new int[105][105][105]();
int T;
cin>>T;
while(T--){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
f[i][j][k]=0;
}
}
}
for(int len=1;len<=n;len++){
for(int i=1,j=len;j<=n;i++,j++){
for(int k=i,l,r;k<=j;k++){
if(~a[k]){
l=r=a[k];
}
else{
l=1,r=n;
}
for(int x=l;x<=r;x++){
(f[i][j][x]+=C(j-i,k-i)*1ll*(i<k?f[i][k-1][x]:1)%mod*(k<j?f[k+1][j][x+1]:1)%mod)%=mod;
}
}
}
}
cout<<f[1][n][1]<<"\n";
}
delete[] fac,inv,a,f;
return 0;
}
}
int main(){return asbt::main();}
啊上面這個(gè)因?yàn)?hdu 評(píng)測(cè)機(jī)太慢過不了，這告訴我們可以用楊輝三角時(shí)就用吧，還有不要用 new 定義數(shù)組。。。
Code
#include<cstdio>
#include<iostream>
#include<functional>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int mod=1e9+7;
int C[105][105],a[105],f[105][105][105];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
for(int i=0;i<=100;i++){
C[i][0]=1;
for(int j=1;j<=i;j++){
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
}
int T;
cin>>T;
while(T--){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
f[i][j][k]=0;
}
}
}
for(int len=1;len<=n;len++){
for(int i=1,j=len;j<=n;i++,j++){
for(int k=i,l,r;k<=j;k++){
if(~a[k]){
l=r=a[k];
}
else{
l=1,r=n;
}
for(int x=l;x<=r;x++){
(f[i][j][x]+=C[j-i][k-i]*1ll*(i<k?f[i][k-1][x]:1)%mod*(k<j?f[k+1][j][x+1]:1)%mod)%=mod;
}
}
}
}
cout<<f[1][n][1]<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
復(fù)雜度看起來假的離譜的 dp 如果常數(shù)小有可能就是真的了……
浙公網(wǎng)安備 33010602011771號(hào)