发布时间：2024-08-30

笛卡尔树

概念

以下标作为val，数值作为key，满足堆性质的平衡树(treap是权值随机的笛卡尔树)

模板

int stk[N],top,ls[N],rs[N],a[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int cur=0;
    for(int i=1;i<=n;i++){
        cur=top;
        while(cur&&a[stk[cur]]>a[i])cur--;
        if(cur)rs[stk[cur]]=i;
        if(cur<top)ls[i]=stk[cur+1];
        stk[++cur]=i;
        top=cur;
    }
}

P1377 [TJOI2011] 树的序

题意：

按给定顺序构造二叉搜索树，问能构造相同的树的字典序最小的生成序列

思路：

• 朴素做法是直接建BST，然后先序遍历，但是有可能退化成链，$O(n^2)$ 超时
• 用笛卡尔树做，转化权值为序列下标，下标变key值即可

void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        a[x]=i;
    }
    int cur=0;
    for(int i=1;i<=n;i++){
        cur=top;
        while(cur&&a[stk[cur]]>a[i])cur--;
        if(cur)rs[stk[cur]]=i;
        if(cur<top)ls[i]=stk[cur+1];
        stk[++cur]=i;
        top=cur;
    }
    dfs(stk[1]);
}

CF1175F

题意：

询问多少个子区间[l,r]满足:

• 最大值为r-l+1
• 每个数字只出现一次

思路：

• 建出大根堆的笛卡尔树
• 枚举横跨当前节点的区间(长度为当前节点权值，枚举一边端点，另一边也就确定了)
• 如何判断一个区间满足条件，记pre[i]为上一次出现i的下标，对pre求前缀max，则有条件pre[r]<l

int a[N],n,stk[N],ls[N],rs[N],lst[N],top,ans;
void dfs(int u,int l,int r){
    if(l>=r){
        if(a[u]==1)ans++;
        return;
    }
    int len=a[u];
    if(u-l+1>=r-u+1){
        for(int i=u;i<=r;i++){
            int L=i-len+1;
            if(L>=l&&L<=u&&lst[i]<L)ans++;
        }
    }
    else{
        for(int i=l;i<=u;i++){
            int R=i+len-1;
            if(R<=r&&R>=u&&lst[R]<i)ans++;
        }    
    }
    if(ls[u])dfs(ls[u],l,u-1);
    if(rs[u])dfs(rs[u],u+1,r);
}   
void solve(){   
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int cur=0;
    for(int i=1;i<=n;i++){
        cur=top;
        while(cur&&a[stk[cur]]<a[i])cur--;
        if(cur)rs[stk[cur]]=i;
        if(cur<top)ls[i]=stk[cur+1];
        stk[++cur]=i;
        top=cur;
    }
    map<int,int > pos;
    for(int i=1;i<=n;i++){
        if(pos.count(a[i]))lst[i]=pos[a[i]];
        pos[a[i]]=i;
        lst[i]=max(lst[i],lst[i-1]);
    }
    dfs(stk[1],1,n);
    cout<<ans<<"\n";
}

河北省赛B

题意：

$$定义区间 [l,r]的值为max(a_l ,...a_r) \cdot min(a_l,...,a_r) \cdot (r-l+1),找第k大的值$$

思路：

• 二分答案，然后计算>=mid的区间有多少个
• 考虑以i下标的值为最小值时，最左和最右能到达的最远距离，可以用单调栈或者悬线法预处理出来
• 然后对于每个点，会有左右两个区间，枚举较小长度的区间作为其中一个端点，对于较长长度的区间，因为区间的值会随长度增大而增大，可以二分出另外一边能到的最远距离，计算答案即可
• 还需要一个st表，在二分区间最远端时来查询区间最值
• 时间复杂度:

  $$O(nlog^3n)$$

• 做法二：直接建笛卡尔树，做笛卡尔树分治
• 两个做法实际上都基于启发式合并的分治，是启发式合并的逆过程，相关习题可以搜索启发式分裂或者笛卡尔树分治，可以搜出许多类似的题目

struct RMQ{
    vector<vector<int>> st;
    int n;
    void init(int a[],int n){
        this->n=n;
        st=vector<vector<int>> (n+1,vector<int> (30,1e9));
        for(int i=1;i<=n;i++)st[i][0]=a[i];
        for(int j=1;j<=25;j++){
            for(int i=1;i+(1<<j)-1<=n;i++)st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
        }
    }
    int query(int l,int r){
        int len=__lg(r-l+1);
        return max(st[l][len],st[r-(1<<len)+1][len]);
    }
} rmq;
int stk[N],ls[N],rs[N],top,cur;
int n,k,a[N];
int get(int l,int r,int mn){
    if(l<1||r>n)return INF*INF;
    return rmq.query(l,r)*mn*(r-l+1);
}
void dfs(int u,int l,int r,int x,int &ans){
    if(u-l<r-u){
        for(int i=l;i<=u;i++){
            int lo=u,hi=r+1;
            while(lo<hi){
                int mid=lo+hi>>1;
                if(get(i,mid,a[u])>=x)hi=mid;
                else lo=mid+1;
            }
            ans+=r+1-lo;
            if(lo==r+1)break;
        }
    }
    else{
        for(int i=r;i>=u;i--){
            int lo=l-1,hi=u;
            while(lo<hi){
                int mid=lo+hi+1>>1;
                if(get(mid,i,a[u])>=x)lo=mid;
                else hi=mid-1;
            }
            ans+=lo-l+1;
            if(lo==l-1)break;
        }
    }
    if(ls[u])dfs(ls[u],l,u-1,x,ans);
    if(rs[u])dfs(rs[u],u+1,r,x,ans);
}
bool check(int mid){
    int ans=0;
    dfs(stk[1],1,n,mid,ans);
    return ans>=k;
}
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    rmq.init(a,n);
    for(int i=1;i<=n;i++){
        cur=top;
        while(cur&&a[stk[cur]]>a[i])cur--;
        if(cur)rs[stk[cur]]=i;
        if(cur<top)ls[i]=stk[cur+1];
        stk[++cur]=i;
        top=cur;
    }
    int l=1,r=1e18;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    cout<<l<<"\n";
}