好写，无分类讨论的建析合树方法

feecle6418 · 2022-06-21 16:37:12 · 个人记录

就递归建。

namespace Maketree{

    int st1[200005],st2[200005],top1,top2,mn[14000005],tag[14000005],c[14000005][2],tot,rt[200005];
    int Find(int p,int l,int r,int x,int y){
        y-=tag[p];
        if(r<x||mn[p]>y)return -1;
        if(l==r)return l;
        int mid=(l+r)>>1,ret=Find(c[p][0],l,mid,x,y);
        if(ret!=-1)return ret;
        return Find(c[p][1],mid+1,r,x,y);
    }
    int Get(int p,int l,int r,int x){
        if(l==r)return tag[p];
        int mid=(l+r)>>1;
        if(x<=mid)return Get(c[p][0],l,mid,x)+tag[p];
        return Get(c[p][1],mid+1,r,x)+tag[p];
    }
    bool Check(int l,int r){
        return Get(rt[r],1,n,l)==0;
    }
    int Build(int l,int r){
        if(l==r)return tp[l]=1,L[l]=R[l]=l,l;
        int p=++N;
        L[p]=l,R[p]=r;
        int cur=r;
        int to=Find(rt[r],1,n,l+1,0);
        if(Check(l,to-1)){
            int lst=l;
            g[p].push_back(Build(l,to-1)),tp[p]=0;
            while(1){
                if(to==r)break;
                int x=Find(rt[r],1,n,to+1,0);
                if(!Check(lst,x-1))break;
                g[p].push_back(Build(to,x-1));
                lst=to,to=x;
            }
            g[p].push_back(Build(to,r));
        }
        else {
            tp[p]=1;
            while(1){
                to=Find(rt[cur],1,n,l+1,0);
                g[p].push_back(Build(to,cur));
                if(Check(l,to-1)){
                    g[p].push_back(Build(l,to-1));
                    break;
                }
                cur=to-1;
            }
            reverse(g[p].begin(),g[p].end());
        }
        return p;
    }
    void Add(int &p,int l,int r,int x,int y,int z){
        int q=++tot;
        mn[q]=mn[p],tag[q]=tag[p],c[q][0]=c[p][0],c[q][1]=c[p][1],p=q;
        if(x<=l&&r<=y)return tag[p]+=z,void();
        int mid=(l+r)>>1;
        if(x<=mid)Add(c[p][0],l,mid,x,y,z);
        if(mid<y)Add(c[p][1],mid+1,r,x,y,z);
        mn[p]=min(mn[c[p][0]]+tag[c[p][0]],mn[c[p][1]]+tag[c[p][1]]);
    }
    void main(){
        for(int i=1;i<=n;i++){
            rt[i]=rt[i-1];
            while(top1&&a[st1[top1]]<a[i])Add(rt[i],1,n,st1[top1-1]+1,st1[top1],a[i]-a[st1[top1]]),top1--;
            while(top2&&a[st2[top2]]>a[i])Add(rt[i],1,n,st2[top2-1]+1,st2[top2],a[st2[top2]]-a[i]),top2--;
            if(i>1)Add(rt[i],1,n,1,i-1,-1);
            st1[++top1]=i;
            st2[++top2]=i;
        }
        root=Build(1,n);
    }

}