笛卡爾樹

說實在的感覺這個東西過于抽象了，只能夠掌握幾種比較套路的笛卡爾樹題目，

要是考場上出一些非常隱含的建樹或者維護，大概是用不出來的，（除非靈光一現）

先放一個建樹的板子

 1 namespace cartesian_tree{
 2     int stk[NN],top,son[NN][2],siz[NN];
 3     inline void build(int *a){
 4         for(int i=1;i<=n;i++){
 5             while(top&&a[stk[top]]<a[i]) son[i][0]=stk[top--];
 6             if(top) son[stk[top]][1]=i;
 7             stk[++top]=i;
 8         }
 9     }
10 }using namespace cartesian_tree;

簡單說一下思想，大多數題目都是以下標滿足二叉搜索樹的性質，陣列元素值滿足小根堆性質建樹的

但是有個題比較特殊（$hdu4125Moles$，他反著來）

這個資料結構一般是拿來找最大子矩形，很多的奇技淫巧都和這棵樹的子樹大小有關

最大子矩形就是$\max\limits_{x=1}^{n}(siz[x]*a[x])$

還有一些放在例題里面說吧，

BZOJ #2616. SPOJ PERIODNI

不難發現是一道$dp$題，然后他最煩的就是各個矩形間會相互影響，這是最不方便的地方

那么我們考慮用笛卡爾樹適當的減少矩形間的相互作用

發現建一個小根堆笛卡爾樹后，一個比較小的子樹根節點會把兩個比較大的兒子矩形分開

這樣兩個兒子矩形高出父親的部分就可以隨便選擇

那么設一個$dp[i][j]$表示以$i$為根的子樹放了$j$輛車的方案數

就可以得到子樹合并時的轉移$g[i+j]=\sum\limits_{i=0}^{siz[ls]} \sum\limits_{j=0}^{siz[rs]} dp[ls][i] \times dp[rs][j]$（$g$是一個轉移陣列）

注意邊界要卡緊，是兩個兒子的$siz$，不能再多選擇了，同樣的他們的父親最多也只能選$siz[x]$輛車

考慮如何計算和父親有重疊的部分，在遞回的程序中傳一個$lim$的參，表示父親的上一層父親的高度

那么圖大概是長這樣的

 就是說從兩個兒子的子樹中轉移來的方案數存到了$g$中，然后還要從$[lim,h_x]\times siz_x$的矩形中選擇一些

那么轉移就是

$dp[x][j]=\sum \limits_{j=0}^{siz_x} \sum\limits_{k=0}^{j}g[j-k] \times k! \times C_{h_x-lim}^{k} \times C_{siz_x-(j-k)}^{k}$

然后注意列舉順序和邊界問題就可以了

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define int long long
 5 const int mod=1e9+7,NN=505,MM=1e6+5;
 6 int n,K,h[NN];
 7 namespace Math{
 8     int jc[MM],ny[MM];
 9     inline int qmo(int a,int b,int ans=1){int c=mod;
10         for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
11         return ans;
12     }
13     inline void pre(){
14         jc[0]=jc[1]=1; ny[0]=ny[1]=1;
15         for(int i=2;i<MM;i++) jc[i]=jc[i-1]*i%mod;
16         ny[MM-1]=qmo(jc[MM-1],mod-2);
17         for(int i=MM-2;i>=2;i--) ny[i]=ny[i+1]*(i+1)%mod;
18     }
19     inline int C(int n,int m){
20         if(n<m||n<0||m<0) return 0;
21         return jc[n]*ny[n-m]%mod*ny[m]%mod;
22     }
23 }using namespace Math;
24 namespace cartesian_tree{
25     int stk[NN],top,son[NN][2],dp[NN][NN],siz[NN],g[NN];
26     inline void build(int *a){
27         for(int i=1;i<=n;i++){
28             while(top&&a[stk[top]]>a[i]) son[i][0]=stk[top--];
29             if(top) son[stk[top]][1]=i;
30             stk[++top]=i;
31         }
32     }
33     inline void dfs(int x,int lim){
34         if(!x) return; siz[x]=1;
35         dfs(son[x][0],h[x]); dfs(son[x][1],h[x]);
36         siz[x]+=siz[son[x][0]]+siz[son[x][1]];
37         int ls=son[x][0],rs=son[x][1],hi=h[x]-lim;
38         for(int i=0;i<=siz[x];i++) g[i]=0;
39         for(int i=0;i<=siz[ls];i++)
40             for(int j=0;j<=siz[rs];j++)
41                 (g[i+j]+=dp[ls][i]*dp[rs][j]%mod)%=mod;
42         for(int j=siz[x];~j;--j)
43             for(int k=0;k<=j;k++)
44                 (dp[x][j]+=g[j-k]*jc[k]%mod*C(hi,k)%mod*C(siz[x]-(j-k),k)%mod)%=mod;
45     }
46 }using namespace cartesian_tree;
47 namespace WSN{
48     inline short main(){
49         scanf("%lld%lld",&n,&K); pre();
50         for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
51         build(h); dp[0][0]=1;
52         dfs(stk[1],0);
53         printf("%lld\n",dp[stk[1]][K]);
54         return 0;
55     }
56 }
57 signed main(){return WSN::main();}

hdu6854Kcats

利用笛卡爾樹思想來做區間$dp$，就是意思是利用笛卡爾樹在構建時子樹下標是一段連續的區間（僅對于下標為陣列下標，鍵值為陣列元素值時成立）

我們發現他給的前綴單調堆疊大小實際上是在說$i$這個節點的到祖先的鏈上有幾個祖先是在他左邊的

 這個是樣例里面給出的關于$1,1,2,3,4,2$的合法方案，$3,1,4,5,6,2$，上面的節點寫的是陣列下標

那么我們$dp$的就是這樣一個樹形的結構，設$f[i][j][d]$表示$i$到$j$的一段區間子樹的根有$d$個左祖先的建樹方案數

然后需要判斷可以轉移的區間范圍，注意在轉移的時候要乘上一個組合數$C_{j-i}^{k-i}$，表示子樹的構建方案

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define int long long
 5 const int NN=105,mod=1e9+7;
 6 int T,n,a[NN],f[NN][NN][NN],C[NN][NN];
 7 namespace WSN{
 8     inline short main(){
 9         scanf("%lld",&T);C[0][0]=1;
10         for(int i=1;i<NN;i++){
11             C[i][0]=C[i][i]=1;
12             for(int j=1;j<i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
13         }
14         while(T--){
15             scanf("%lld",&n); memset(f,0,sizeof(f));
16             for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
17             for(int i=n;i;i--){
18                 for(int j=i;j<=n;j++){
19                     for(int k=i;k<=j;k++){
20                         int l,r; (a[k]==-1)?(l=1,r=n):(l=r=a[k]);
21                         for(int d=l;d<=r;d++){
22                             int t1=(i==k?1:f[i][k-1][d]);
23                             int t2=(j==k?1:f[k+1][j][d+1]);
24                             (f[i][j][d]+=t1*t2%mod*C[j-i][k-i]%mod)%=mod;
25                         }
26                     }
27                 }
28             }
29             printf("%lld\n",f[1][n][1]);
30         }
31         return 0;
32     }
33 }
34 signed main(){return WSN::main();}

以上是在做笛卡爾樹專題里比較妙的兩道題，再有就是那個$Moles$，

提一下就好了，就是反著建樹，原來笛卡爾樹的二元組$(k,w)$分別表示陣列下標和元素值

這道題里面二元組$(k,w)$表示元素值和陣列下標

標籤：C++

上一篇：有沒有辦法在iOS專案上禁用xamarin.forms.maps上的資訊視窗？

下一篇：XamarinListView備用列顏色