主席树经典应用区间合并

曾经终败给现在 2022-09-05 00:06 172阅读 0赞

线段树经典应用2  
![在这里插入图片描述][221b2f2385234a159141a3f1b5c11a55.png]

参考代码：

https://vjudge.net/problem/CodeForces-484E
    
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll long long
    const int maxn=1e5+10;
    struct node
    {
        int s[2];
        int lmx,rmx,f,len;
    };
    int rt[maxn],n;
    struct sgt_tree
    {
        #define ls (t[u].s[0])
        #define rs (t[u].s[1])
        int tot=0;
        node t[maxn*40];
        int build(int l,int r)
        {
            int u=++tot;
            if(l==r)
            {
                t[u].lmx=t[u].rmx=t[u].f=0;
                t[u].len=1;
                return u;
            }
            int mid=(l+r)/2;
            t[u].s[0]=build(l,mid);
            t[u].s[1]=build(mid+1,r);
            pushup(u,l,r);
            return u;
        }
        void pushup(int u,int l,int r)
        {
            t[u].len=t[ls].len+t[rs].len;
    
            int mid=(l+r)>>1;
            if(t[ls].f==(mid-l+1))t[u].lmx=t[ls].f+t[rs].lmx;
            else t[u].lmx=t[ls].lmx;
    
            if(t[rs].f==(r-mid))t[u].rmx=t[rs].f+t[ls].rmx;
            else t[u].rmx=t[rs].rmx;
    
            t[u].f=max(max(t[ls].f,t[rs].f),t[ls].rmx+t[rs].lmx);
        }
        int insert(int oldrt,int l,int r,int pos)
        {
            int u=++tot;
            t[u]=t[oldrt];
            if(l==r)
            {
                t[u].lmx=t[u].rmx=t[u].f=1;
                t[u].len=1;
                return u;
            }
            int mid=(l+r)>>1;
            if(pos<=mid)t[u].s[0]=insert(t[oldrt].s[0],l,mid,pos);
            else t[u].s[1]=insert(t[oldrt].s[1],mid+1,r,pos);
            pushup(u,l,r);
            return u;
        }
        void query(int u,int l,int r,int ql,int qr,int&res,int&tolmx)
        {
            if(l>qr||r<ql)return;
            if(ql<=l&&r<=qr)
            {
                res=max(res,t[u].f);
                tolmx+=t[u].lmx;
                res=max(res,tolmx);
                if(t[u].len!=t[u].lmx)
                    tolmx=t[u].rmx;
                res=max(res,tolmx);
                return;
            }
            int mid=(l+r)>>1;
            query(ls,l,mid,ql,qr,res,tolmx);
            query(rs,mid+1,r,ql,qr,res,tolmx);
        }
        #undef ls
        #undef rs
    }sgt;
    struct query
    {
        int h,id;
        bool operator <(const query x)const{
            return h>x.h;
        }
    }fe[maxn];
    
    int main()
    {
        scanf("%d", &n);
    	for (int i = 1; i <= n; i++)
    	{
    		int x;
    		scanf("%d", &x);
    		fe[i].h = x; fe[i].id = i;
    	}
    	sort(fe+1,fe+n+1);
    	rt[0]=sgt.build(1,n);
    	for (int i = 1; i <= n; i++)
    		rt[i]= sgt.insert(rt[i - 1],1,n,fe[i].id);
    
        int T_T;
        scanf("%d",&T_T);
        while(T_T--)
        {
            int L,R,W;
            scanf("%d%d%d",&L,&R,&W);
            int low=1,high=n,ans;
            while(low<=high)
            {
                int mid=(low+high)/2;
                int toleft=0,res=0;
                sgt.query(rt[mid],1,n,L,R,res,toleft);
                if(res>=W)
                {
                    ans=mid;
                    high=mid-1;
                }else low=mid+1;
            }
            printf("%d\n",fe[ans].h);
        }
    
        return 0;
    }

high=mid-1;
            }else low=mid+1;
        }
        printf("%d\n",fe[ans].h);
    }
    
    return 0;

[221b2f2385234a159141a3f1b5c11a55.png]: /images/20220829/77c2f51b9f4d4f2d9ddc6a89b902d2ae.png