對于一個序列建立的笛卡爾樹滿足：

• 它是個二叉樹。

• 若以下標為關鍵字，笛卡爾樹滿足二叉搜索樹性質(若以每個點一下都包含一段連續的區間)。

• 若以權值為關鍵字，它是一個小根堆。

• 若權值互不相同，那么這個序列的笛卡爾樹唯一(當然，若權值相同，就會有很多棵樹，于是就有笛卡爾樹計數啦)。

它具有這么多優秀的性質，當然可以干很多事情啦。

(以上圖片來自維基百科)

建立

維護一個棧維護從隊列第一個元素到現在的遞增子序列(存的當然是下標)，接下來分類討論：

• 若新增元素大于等于棧頂，那么直接進棧并與接到此時棧頂右兒子。

• 否則一直彈棧直到小于棧頂，將最后彈出的元素連到當前元素的左兒子，之后進站并連邊棧頂。

sta[rt=tp=1]=1; for(int i=2;i<=n;i++) {if(a[i]>=a[sta[tp]]) ch[sta[tp]][1]=i,sta[++tp]=i;else{while(a[i]<a[sta[tp]]) tp--;if(!tp) rt=i;ch[i][0]=sta[tp+1];ch[sta[tp]][1]=i;sta[++tp]=i;} }

笛卡爾樹計數

笛卡爾樹滿足根節點的的權值小于等于兒子節點的權值。

那么對于給定的一個數列，這個序列中所有的最小值一定都直接連接在根節點上。

設有 \(m\) 個最小值，則這些節點可以組成的二叉樹個數……

就是卡特蘭數的第 \(m\) 項啦！

如上圖，將最小值提取出后，可以將原序列分成若干段，分別求解最小值即可。

$\texttt{code}$ #define Maxn 1000005 #define Maxpown 21 #define mod 1000000007 typedef long long ll; inline int rd() {int x=0;char ch,t=0;while(!isdigit(ch = getchar())) t|=ch=='-';while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();return x=t?-x:x; } int n; int st[Maxn][Maxpown],pos[Maxn][Maxpown]; int pow2[Maxpown],lg[Maxn]; ll Cart[Maxn],inv[Maxn<<1],mi[Maxn<<1],invmi[Maxn<<1]; inline ll C(int x,int y) { return mi[x]*invmi[x-y]%mod*invmi[y]%mod; } inline ll ksm(ll x,ll y) {ll ret=1;while(y){if(y&1) ret=ret*x%mod;x=x*x%mod,y>>=1;}return ret; } inline int query_pos(int l,int r) {int p=lg[r-l+1]-1;if(st[l][p]<=st[r-pow2[p]+1][p]) return pos[l][p];return pos[r-pow2[p]+1][p]; } inline int query_min(int l,int r) {int p=lg[r-l+1]-1;return min(st[l][p],st[r-pow2[p]+1][p]); } ll Find(int l,int r) {if(l>r) return 1;ll ret=1;int Last=l,fir,cnt=0,Least=query_min(l,r),Now;while(Last<=r){Now=query_min(Last,r);if(Now>Least) { ret=ret*Find(Last,r); break; }fir=query_pos(Last,r);ret=ret*Find(Last,fir-1)%mod;Last=fir+1,cnt++;}ret=ret*Cart[cnt]%mod;return ret; } int main() {n=rd(),pow2[0]=1;for(int i=1;i<=n;i++) st[i][0]=rd(),pos[i][0]=i;inv[0]=mi[0]=invmi[0]=inv[1]=mi[1]=invmi[1]=1;for(ll i=2;i<=n+n;i++){mi[i]=mi[i-1]*i%mod;inv[i]=(mod-mod/i)*inv[mod%i]%mod;invmi[i]=invmi[i-1]*inv[i]%mod;}for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;for(ll i=1;i<=n;i++) Cart[i]=C(i+i,i)*ksm(i+1,mod-2)%mod;for(int i=1;i<=20;i++) pow2[i]=pow2[i-1]*2;for(int i=1;i<=20;i++)for(int j=1;j<=n-pow2[i]+1;j++){if(st[j][i-1]<=st[j+pow2[i-1]][i-1])pos[j][i]=pos[j][i-1];else pos[j][i]=pos[j+pow2[i-1]][i-1];st[j][i]=min(st[j][i-1],st[j+pow2[i-1]][i-1]);}printf("%lld\n",Find(1,n));return 0; }

直方圖最大子矩形

這道題可以用單調棧，也可以用笛卡爾樹！

一個笛卡爾樹上的點 \(x\) 以及其子樹表示大于等于 \(val(x)\) 的整個區間。

所以 \(ans=\max\{val(x)\times siz(x)\}\)。

$\texttt{code}$ #define Maxn 100005 int n,tp,rt; ll ans; int a[Maxn],siz[Maxn],sta[Maxn]; int ch[Maxn][2]; inline void build() {sta[rt=tp=1]=1,ans=0;for(int i=2;i<=n;i++){if(a[i]>=a[sta[tp]]) ch[sta[tp]][1]=i,sta[++tp]=i;else{while(a[i]<a[sta[tp]]) tp--;if(!tp) rt=i;ch[i][0]=sta[tp+1];ch[sta[tp]][1]=i;sta[++tp]=i;}} } void dfs(int x) {siz[x]=1;for(int i=0;i<2;i++) if(ch[x][i])dfs(ch[x][i]),siz[x]+=siz[ch[x][i]];ans=maxll(ans,1ll*a[x]*siz[x]); } int main() {while((n=rd())!=0){for(int i=1;i<=n;i++) a[i]=rd(),ch[i][0]=ch[i][1]=0;build(),dfs(rt);printf("%lld\n",ans);}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的笛卡尔树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。