学习笛卡尔树

笛卡尔树(知识总结+板子整理)

笛卡尔树

例题1:hdu-6305

RMQ Similar Sequence

【题意】：

题意：定义RMQ(A,l,r)为：序列A中，满足A[i] = max(A[l],A[l+1],...,A[r])的最小的i。如果对于任意(l,r)都满足RMQ(A,l,r)=RMQ(B,l,r)则为A和B是RMQ Similar。现在出A序列，B序列的每个数都是0~1之间的实数，问满足与A是RMQ Similar的所有B序列中所有数之和的期望。

题解：不难看出如果A和B是RMQ Similar，则A和B的笛卡尔树同构。考虑B中的每个数是0~1之间的实数，因此出现相同数字的概率为0，可以假设B是每个数都不相同排列。设A的笛卡尔树每个子树的大小为sz[u]，则任一B排列与A同构的概率是，因为B中每个数满足均匀分布，因此期望值为1/2，和的期望为n/2，因此满足与A同构的B中所有数之和的期望为

所以求：sz[i] 指的是笛卡尔树每个子树的大小。

贴上代码：

#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5 ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
inline int read(){
    int x = 0 , f = 1 ;
    char c = getchar();
    while ( c < '0' || c > '9' ) {
        if( c=='-' ) f = -1 ;
        c = getchar();
    }
    while ( '0' <= c && c <= '9' ){
        x = x*10 + c-'0';
        c = getchar();
    }
    return x * f ;
}
typedef struct Node{
    int val,fa,sz;
    int L,R;
    Node(){}
}Node;
Node t[N];
stack<int>st;
void Init(int n){
    for(int i=0;i<=n;i++){
        t[i].sz = t[i].L = t[i].R = t[i].fa = 0;
    }
    t[0].val = INF;
    while(!st.empty()) st.pop();
    st.push(0);
}

void build(int n){
    int k ;
    for(int i=1;i<=n;i++){
        while( !st.empty() && t[st.top()].val < t[i].val )
            st.pop();
        k = st.top();
        t[i].L = t[k].R;
        t[k].R = i ;
        t[i].fa = k;
        t[t[i].L].fa = i ;
        st.push(i);
    }
}
void dfs(int u) {
    if ( !u ) return ;
    t[u].sz = 1 ;
    dfs( t[u].L );
    dfs( t[u].R );
    t[u].sz += t[t[u].L].sz
            + t[t[u].R].sz ;
}
ll inv[N];
void Init() {
    inv[1] = 1;
    for (int i = 2; i < N; i++)
        inv[i] = inv[mod % i] * (mod - mod / i) % mod;
}
int main()
{
    int T,n;
    Init();
    for ( scanf("%d",&T) ; T ; T-- ){

        n = read();
        Init(n);
        for(int i=1;i<=n;i++){
            t[i].val = read() ;
        }
        //puts("####");

        build(n);
        dfs(t[0].R);

        ll ans=n *inv[2]%mod;
        for(int i=1;i<=n;i++)
            ans=ans*inv[t[i].sz]%mod;

        printf("%lld
",ans);
    }
    return 0;
}
/*
3
3
1 2 3
3
1 2 1
5
1 2 3 2 1
*/

【例题2】poj-2201

Cartesian Tree

题目大意：裸的笛卡尔树，建树输出每个点的父节点和儿子节点编号，没有为0。

构造一颗笛卡尔树，然后输出这棵树即可。

首先进行排序，然后用一个栈维护最右的树的节点信息，插入的时候按照第二关键字去找，找到之后插入，下面的树成为它的左子树即可。

然后插入分三种情况讨论（最下面，中间，成为了新的树根）

题目分析：注意这题肯定要输出YES，因为给的每一对关键字都不相同，所以能建唯一的笛卡尔树，不存在NO的情况。还有排序后序号就乱了，注意一下就行了，其他的没什么了。

#include<cstdio>
#include<algorithm>
const int N = 5e4+5;
using namespace std;
typedef struct Node{
    int id , L , R , val , key ,fa ;
    bool operator < (const Node &rhs )const {
        return key < rhs.key ;
    }
}Node ;
Node t[N];
int n,L[N],R[N],st[N],Fa[N];
void build(){
    int top = 0 ;
    st[top] = 1 ;
    for(int i=2;i<=n;i++){
        while( top >= 0 && t[st[top]].val > t[i].val )
            top -- ;
        if ( top > -1  ){
            t[i].L = t[st[top]].R;
            t[st[top]].R = i ;
            t[i].fa = st[top];
            t[t[i].L].fa = i ;
        }else{
            t[st[0]].fa = i ;
            t[i].L = st[0];
        }
        st[++top] =  i ;
    }
}

int main()
{
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            scanf("%d%d",&t[i].key,&t[i].val);
            t[i].id = i ;
            t[i].L = t[i].R = t[i].fa = 0 ;
        }
        sort( t+1 , t+1+n ) ;
        build();
        for(int i=1;i<=n;i++){
            Fa[t[i].id] = t[t[i].fa].id;
            L[t[i].id] = t[t[i].L].id ;
            R[t[i].id] = t[t[i].R].id ;
        }
        puts("YES");
        for(int i=1;i<=n;i++){
            printf("%d %d %d
",Fa[i],L[i],R[i]);
        }
    }
    return 0;
}
/*

7
5 4
2 2
3 9
0 5
1 3
6 6
4 11

YES
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0
 */