介紹

笛卡爾樹(shù)是一種非常特殊的二叉搜索樹(shù)。每個(gè)節(jié)點(diǎn)有兩個(gè)信息x和y。如果只考慮 x，它是一棵二叉搜索樹(shù)，如果只考慮 y，它是一個(gè)小根堆。

實(shí)現(xiàn)

按照y升序插入
顯然應(yīng)該插入到一條極右鏈上
但為了維護(hù)x二叉搜索樹(shù)的性質(zhì)
對(duì)于右鏈上x(chóng)>當(dāng)前元素的點(diǎn)應(yīng)該接到當(dāng)前元素的左兒子上
從而保證兩個(gè)性質(zhì)均符合
實(shí)現(xiàn)可以用單調(diào)棧線(xiàn)性解決

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned ll #define mid ((l+r)>>1) const int N=1e7+100; int n,m,tot; int zhan[N],p[N],l[N],r[N],top,lst; void insert(int x){lst=0;while(top&&p[zhan[top]]>p[x]){lst=zhan[top--];}if(top) r[zhan[top]]=x;if(lst) l[x]=lst;zhan[++top]=x; } int read(){int x=0,f=0;char c=getchar();while(c<'0'||c>'9') f=c=='-',c=getchar();while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48),c=getchar();}return f?-x:x; } int main(){n=read();for(int i=1;i<=n;i++) p[i]=read();for(int i=1;i<=n;i++) insert(i);ll res=0;for(int i=1;i<=n;i++) res^=1ll*i*(l[i]+1);printf("%lld ",res);res=0;for(int i=1;i<=n;i++) res^=1ll*i*(r[i]+1);printf("%lld",res);return 0; } /* 5 5 1 5 7 6 2 1 5 2 1 5 3 1 3 9 2 4 2 3 5 5 */

應(yīng)用

笛卡爾樹(shù)可以用來(lái)解決RMQ問(wèn)題
[l,r]的極值就是l、r對(duì)應(yīng)結(jié)點(diǎn)的lca
不過(guò)為什么不用st表O1解決呢

總結(jié)

以上是生活随笔為你收集整理的模板：笛卡尔树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。