------------恢复内容开始------------

P3380 【模板】二逼平衡树（树套树） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

线段树套平衡树，代码是前几个月写的，fhq套线段树

#include<bits/stdc++.h>
#define maxn 50050
#define maxm 1000010
using namespace std;
const int inf=2147483647;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node
{
    int l,r,root;
}tt[maxn<<2];
int a[maxn],n,m;
int cnt=0;
struct fhq_node
{
  int ch[2],key,val,siz; 
}t[maxm<<1];
inline int newnode(int data)
{
    int k=++cnt;
    t[k].key=rand();
    t[k].val=data;
    t[k].siz=1;
    t[k].ch[0]=t[k].ch[1]=0;
    return k;
}
inline void update(int k)
{
    t[k].siz=t[t[k].ch[0]].siz+t[t[k].ch[1]].siz+1;
}
int merge(int l,int r)
{
    if(!l||!r) return l+r;
    if(t[l].key>t[r].key)
    {
        t[l].ch[1]=merge(t[l].ch[1],r);
        update(l);
        return l;
    }
    else
    {
        t[r].ch[0]=merge(l,t[r].ch[0]);
        update(r);
        return r;
    }
}
void split(int k,int val,int &l,int &r)
{
    if(!k)
    {
        l=r=0;
        return ;
    }
    if(val>=t[k].val)
    {
        l=k;
        split(t[l].ch[1],val,t[l].ch[1],r);
    }
    else
    {
        r=k;
        split(t[r].ch[0],val,l,t[r].ch[0]);
    }
    update(k);
}
void insert(int &root,int data)
{
    int l=0,r=0;
    split(root,data,l,r);
    root=merge(merge(l,newnode(data)),r);
}
void delet(int &root,int data)
{
    int l=0,p=0,r=0;
    split(root,data,l,r);
    split(l,data-1,l,p);
    p=merge(t[p].ch[0],t[p].ch[1]);
    root=merge(l,merge(p,r));
}
void build(int i,int l,int r)
{
    tt[i].l=l;
    tt[i].r=r;
    if(l==r)
    {
        tt[i].root=newnode(a[l]);
        return ;
    }
    for(int k=l;k<=r;k++)
    {
        insert(tt[i].root,a[k]);
    }
    int m=(l+r)>>1;
    build(i*2,l,m);
    build(i*2+1,m+1,r);
}
int find_rank(int &root,int data)
{
    int l=0,r=0;
    split(root,data-1,l,r);
    int ans=t[l].siz;
    root=merge(l,r);
    return ans;
}
int rank(int i,int l,int r,int d)
{
    if(l<=tt[i].l && tt[i].r<=r)
    {
        return find_rank(tt[i].root,d);
    }
    int m=(tt[i].l+tt[i].r)>>1;
    int val=0;
    if(l<=m) val+=rank(i*2,l,r,d);
    if(r>m) val+=rank(i*2+1,l,r,d);
    return val;
}
int kth(int l,int r,int k)
{
    int L=0,R=1e8+1,ans=0;
    while(L<R)
    {
        int m=(L+R)>>1;
        if(rank(1,l,r,m)+1<=k)
        {
            ans=m;
            L=m+1;
        }
        else
        R=m;
    }
    return ans;
}
void change(int i,int pos,int data)
{
    delet(tt[i].root,a[pos]);
    insert(tt[i].root,data);
    if(tt[i].l==tt[i].r) return ;
    int m=(tt[i].l+tt[i].r)>>1;
    if(pos<=m) change(i*2,pos,data);
    else
    {
        change(i*2+1,pos,data);
    }
}
int find_pre(int &root,int data)
{
    int l=0,r=0;
    split(root,data-1,l,r);
    int k=l;
    if(!k) return -inf;
    while(t[k].ch[1]) k=t[k].ch[1];
    int ans=t[k].val;
    root=merge(l,r);
    return ans;
}
int find_nxt(int &root,int data)
{
    int l=0,r=0;
    split(root,data,l,r);
    int k=r;
    if(!k) return inf;
    while(t[k].ch[0]) k=t[k].ch[0];
    int ans=t[k].val;
    root=merge(l,r);
    return ans;
}
int ask_pre(int i,int l,int r,int d)
{
    if(l<=tt[i].l && tt[i].r<=r)
    {
        return find_pre(tt[i].root,d);
    }
    int m=(tt[i].l+tt[i].r)>>1;
    int val=-inf;
    if(l<=m)
    {
        val=max(val,ask_pre(i*2,l,r,d));
    }
    if(r>m)
    {
        val=max(val,ask_pre(i*2+1,l,r,d));
    }
    return val;
}
int ask_nxt(int i,int l,int r,int d)
{
    if(l<=tt[i].l&&tt[i].r<=r)
    {
        return find_nxt(tt[i].root,d);
    }
    int m=(tt[i].l+tt[i].r)>>1;
    int val=inf;
    if(l<=m)
    {
        val=min(val,ask_nxt(i*2,l,r,d));
    }
    if(r>m)
    {
        val=min(val,ask_nxt(i*2+1,l,r,d));
    }
    return val;
}
int main()
{
    srand(time(0));
    n=read();
    m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int opt;
        int l,r,k;
        cin>>opt;
        if(opt==1)
        {
            l=read();r=read();k=read();
            cout<<rank(1,l,r,k)+1<<endl;
        }
        else if(opt==2)
        {
            l=read();r=read();k=read();
            cout<<kth(l,r,k)<<endl;
        }
        else if(opt==3)
        {
            int pos,v;
            pos=read();v=read();
            change(1,pos,v);
            a[pos]=v;
        }
        else if(opt==4)
        {
            l=read();r=read();k=read();
            cout<<ask_pre(1,l,r,k)<<endl;
        }
        else
        {
            l=read();r=read();k=read();
            cout<<ask_nxt(1,l,r,k)<<endl;
    }
    }
    
    return 0;
}

View Code

P1975 [国家集训队]排队 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

之前用分块A掉了这个题，但是为了保证大数据下仍然稳定的复杂度，我们仍然需要用稳定的数据结构去解决。

很明显就是要维护区间里比某个数值大的数的数量，树状数组套权值线段树即可，当然你要树状数组套平衡树，也不是不可以啰。

------------恢复内容结束------------