Steven_Meng's Blog

传送门
树套树模板题（线段树套$\rm FHQ Treap$）
一开始听说$\rm FHQ Treap$常数大，会$\rm TLE$，就没敢写，最后发现$\rm FHQ Treap$还是能过的。

好了步入正题：
考虑在线段树的每个节点开一棵$\rm FHQ Treap$，维护的是线段树左右端点$[l,r]$所代表的区间$a_l...a_r$
这样不会$\rm MLE$，因为线段树最多有$\log n$层，而每一层就算填满也只有$O(n)$的空间，所以总空间复杂度是$O(n \log n)$，注意数组要开这么大

$1.$建树：对于节点$[l,r]$，暴力插入$a[l]...a[r]$，时间复杂度$O(n\log^2n)$。
$2.$替换$a[pos]$为$k$：对于包含$pos$的区间$[l,r]$，先删除$a[pos]$，再加入$k$，时间复杂度$O(\log^2n)$。
$3.$查询区间中$num$的排名：我们发现：$num$的排名为区间中小于$num$的数的数量$+1$，又发现线段树的区间查询操作其实将查询区间$[L,R]$分成许多不相交的小区间，根据这个，我们把$num$在小区间的排名$-1$，得到在小区间中小于$num$的数的数量，最后相加，发现小于$num$的数的数量不会重复计算，于是把和$+1$，得到$num$在区间$[L,R]$的排名，时间复杂度$O(\log^2n)$
这里很容易跳进的坑：不能把$num$在小区间中的排名相加，否则$num$会重复算很多次
$4.$查询区间第$k$大的数：因为$\rm FHQ Treap$只能查询$num$的排名，所以考虑二分$num$，时间复杂度$O(\log^3n)$，查询$num$排名$O(\log^2n)$，二分$O(\log n)$。
（当然按照子树大小$\rm Split$，$\rm FHQTreap$也阔以支持查询第$k$大，详情请戳这里）
$5.$查询区间中，$num$的前驱：直接把小区间中$num$的所有前驱取个$max$。
$6.$查询区间中，$num$的后继：类似$5.$

注意要判断$num$的前驱后继是否存在，若不存在，相应地输出$\rm INF/-INF$。
还有修改操作做完后，要执行$a[pos]=k$，修改$a$数组。

#include <bits/stdc++.h>
#define MAXN 50005
#define MAXM 10000005
#define INF 0x7fffffff
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        x=(x*10)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN];
struct node{
	int l,r;
	int val;//每个点的权值 
	int pri;//优先级（随机生成）
	int sz;
}tree[MAXM];
int tot;
struct FHQ_Treap{
	#define lc(i) tree[i].l
	#define rc(i) tree[i].r
	inline void Update(int x){tree[x].sz=tree[lc(x)].sz+tree[rc(x)].sz+1;}
	inline int New(int v){
		tree[++tot].val=v,tree[tot].pri=rand(),tree[tot].sz=1;
		return tot;
	}
	int Merge(int x,int y){
		if (!x||!y) return x+y;
		if (tree[x].pri<tree[y].pri){
            rc(x)=Merge(rc(x),y),Update(x);
            return x;
        }
		else{
            lc(y)=Merge(x,lc(y)),Update(y);
			return y;
        }
	}
	void Split(int i,int k,int &x,int &y){
		if (!i) x=y=0;
		else {
			if (tree[i].val<=k){x=i,Split(rc(i),k,rc(i),y);}
			else{y=i,Split(lc(i),k,x,lc(i));}
			Update(i);
		}
	}
    int root,x,y,z;
    inline void Add(int num){
		Split(root,num,x,y);
		root=Merge(x,Merge(New(num),y));
    }
    inline void Del(int num){
		Split(root,num,x,z);
		Split(x,num-1,x,y);
		y=Merge(lc(y),rc(y));
		root=Merge(Merge(x,y),z);
    }
    inline int Rank(int num){//获得num排名
        Split(root,num-1,x,y);
        int temp=tree[x].sz+1;
		root=Merge(x,y);
        return temp;
    }
    inline int Kth(int i,int rk){
    	if (rk<=tree[lc(i)].sz) return Kth(lc(i),rk);
    	if (rk==tree[lc(i)].sz+1) return tree[i].val;
    	return Kth(rc(i),rk-tree[lc(i)].sz-1);
	}
	inline int Pre(int num){
		Split(root,num-1,x,y);
		int ans=tree[x].sz?Kth(x,tree[x].sz):-INF;
		root=Merge(x,y);
		return ans;
	}
	inline int Nex(int num){
		Split(root,num,x,y);
		int ans=tree[y].sz?Kth(y,1):INF;
		root=Merge(x,y);
		return ans;
	}
    inline void BuildTree(int l,int r){
        for (register int i=l;i<=r;++i){Add(a[i]);}
    }
    #undef lc
    #undef rc
}T[MAXN<<2];
int n;
namespace SegmentTree{
    #define lc i<<1
    #define rc i<<1|1
    void Build(int i,int l,int r){
        T[i].BuildTree(l,r);
        if (l==r) return ;
        int mid=(l+r)>>1;
        Build(lc,l,mid);
        Build(rc,mid+1,r);
    }
    int qrank(int i,int l,int r,int L,int R,int val){
        if (L<=l&&r<=R) {
            return T[i].Rank(val)-1;
        }
        int mid=(l+r)>>1;
        int ans=0;
        if (L<=mid) ans+=qrank(lc,l,mid,L,R,val);
        if (mid<R) ans+=qrank(rc,mid+1,r,L,R,val);
        return ans;
    } 
    inline int qval(int l,int r,int rk){
        int L=0,R=0x7fffffff;
        int ans=-1;
        while (L<=R){
            int mid=(L+R)>>1;
            if (qrank(1,1,n,l,r,mid)<rk) ans=mid,L=mid+1;
            else R=mid-1;
        }
        return ans;
    }
    void Update(int l,int r,int i,int k,int pos){//a[pos]=>k
        T[i].Del(a[pos]),T[i].Add(k);
        if (l==r) return ;
        int mid=(l+r)>>1;
        if (pos<=mid) Update(l,mid,lc,k,pos);
        else Update(mid+1,r,rc,k,pos);
    }
    int qpre(int i,int l,int r,int L,int R,int val){
        if (L<=l&&r<=R){
            return T[i].Pre(val);
        }
        int mid=(l+r)>>1;
        int ans=-0x7fffffff;
        if (L<=mid) ans=max(ans,qpre(lc,l,mid,L,R,val));
        if (mid<R) ans=max(ans,qpre(rc,mid+1,r,L,R,val));
        return ans;
    }
    int qnex(int i,int l,int r,int L,int R,int val){
        if (L<=l&&r<=R){
            return T[i].Nex(val);
        }
        int mid=(l+r)>>1;
        int ans=0x7fffffff;
        if (L<=mid) ans=min(ans,qnex(lc,l,mid,L,R,val));
        if (mid<R) ans=min(ans,qnex(rc,mid+1,r,L,R,val));
        return ans;
    }
    #undef lc
    #undef rc
}
using namespace SegmentTree;
int main(){
    n=read();int m=read();
    for (register int i=1;i<=n;++i){
        a[i]=read();
    }
    Build(1,1,n);
    while (m--){
        int opr=read();
        if (opr==1){
            int l=read(),r=read(),k=read();
            printf("%d\n",qrank(1,1,n,l,r,k)+1);
        }
        else if (opr==2){
            int l=read(),r=read(),k=read();
            printf("%d\n",qval(l,r,k));
        }
        else if (opr==3){
            int pos=read(),k=read();
            Update(1,n,1,k,pos),a[pos]=k;
        }
        else if (opr==4){
            int l=read(),r=read(),k=read();
            printf("%d\n",qpre(1,1,n,l,r,k));
        }
        else if (opr==5){
            int l=read(),r=read(),k=read();
            printf("%d\n",qnex(1,1,n,l,r,k));
        }
    }
}