粗略的学习了一下笛卡尔树 主要是为了平衡树打基础吧 因为关于平衡树 treap 早忘了 splay 不信任复杂度 然后 我能学一种比较简单的树Y
笛卡尔树.这里以建出小根堆为例。描述区间性质的树 可以当成二叉搜索树不过并不平衡因为每次都是选取当前区间最小值当做为根 然后显然根据区间的数的排列不同树的形态也不相同。
所以查找 插入等操作显然不适合它 。能做什么？(我也不知道23333...应该有一定的作用 比如说可以求...
卡尔树中的一个点代表的是一段位置，这段位置就是中序遍历这个点的子树得到的那段连续区间...
过多我也不会了 也不敢口胡挺简单的一个东西。qwq
其实就是这个东西 考虑怎么构造出来一个比较简单的做法是 单调栈 维护整棵树的右链轻松完成构造 复杂度O(n)
还有其他的构造方法最简单的就是递归构造法每次暴力扫描最小的那个数字 然后qwq.. 复杂度O(n^2)
还有 递归构造的时候 考虑线段树维护区间最小值 于是复杂度降到了 nlogn。。
这里推荐直接O(n)非常简单比线段树不知道高到哪里去了。
//#include<bits/stdc++.h> #include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define ll long long #define INF 1000000000 #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define us unsigned #define mod 1000000007 #define db double using namespace std; const int MAXN=100010; int n,rt,top; ll ans; int a[MAXN]; int st[MAXN],s[MAXN][2],f[MAXN]; inline void dfs(int x,int l,int r) { ll sz=r-l+1; ans=max(ans,sz*a[x]); if(s[x][0])dfs(s[x][0],l,x-1); if(s[x][1])dfs(s[x][1],x+1,r); } int main() { freopen("1.in","r",stdin); while(1) { scanf("%d",&n);ans=0; if(!n)break; top=ans=0; for(int i=1;i<=n;++i)scanf("%d",&a[i]),f[i]=s[i][0]=s[i][1]=0; for(int i=1;i<=n;++i) { while(top&&a[st[top]]>a[i])s[i][0]=st[top--]; if(top)f[i]=st[top],s[st[top]][1]=i; st[++top]=i; } rt=st[1];dfs(rt,1,n);printf("%lld\n",ans); } return 0; }
原文：https://www.cnblogs.com/chdy/p/11702779.html
