洛谷 P3380 【【模板】二逼平衡树（树套树）】

其实比想象中的好理解啊

所谓树套树，就是在一棵树的基础上，每一个节点再维护一棵树

说白了，就是为了实现自己想要的操作和优秀的时间复杂度，来人为的增加一些毒瘤数据结构来维护一些什么东西

比如说这道题

如果只求一个区间内的一个数是否是最大值或者最小值，我们显然可以用线段树轻轻松松地解决这个问题

但是现在我们要求一个区间内一个数是否是k大值，那么这个东西我们就可以很显然的用平衡树来解决这个问题

即对每一个区间都单独维护一棵平衡树，然后利用线段树的外壳，将得到的各个区间内的答案进行合并

然后，这道题除了码量极大，常数极难卡，好像就没有什么可以做的了

好了，还是来说一下每一个操作的具体做法

操作一，就像上文所说的那样，对每一个与询问区间有关的区间进行求\(rank\)操作，然后合并。

操作二，由于线段树不能够很好的满足我们的要求，所以我们可以选择利用已经写好了的操作一，对这个数进行二分处理，然后对于每一个二分出的数字，进行操作一判定

操作三，暴力修改即可，对于每一棵包含这个位置的平衡树，先将原数删除，再插入新数

操作四&操作五两种做法

做法一：你可以选择偷懒，先利用操作一，求出其排名，再利用操作二，求出排名-1（+1）的数字

做法二：对于区间中的每一棵平衡树，对其进行求前驱（后继）操作，然后再取最大（最小）值。

完结撒花~

下面是本人为了偷懒写得又丑，常数又大的线段树套Splay的代码：

// luogu-judger-enable-o2

#include<cstdio>

#include<iostream>

#define dir(p) (son[fa[p]][1]==p)

using namespace std;

const int maxn=4e6+10;

int inline read()

{

    int num=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9')

    {

        if(ch=='-') f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')

    {

        num=num*10+ch-'0';

        ch=getchar();

    }

    return num*f;

}

int n,m;

int siz[maxn],son[maxn][2],fa[maxn],num[maxn],tot[maxn],cnt;

void upd(int t){

    	siz[t]=siz[son[t][1]]+siz[son[t][0]]+tot[t];

}

void rot(int p){

    int fp=fa[p],ffp=fa[fp],way=dir(p);

   	son[fp][way]=son[p][way^1];

    fa[son[p][way^1]]=fp;

    son[ffp][dir(fp)]=p;

    fa[p]=ffp;

    son[p][way^1]=fp;

    fa[fp]=p;

    upd(fp),upd(p);

}

struct Splay{

    int root;

    void splay(int p,int g)

    {

    	while(fa[p]!=g)

    	{

        	int fp=fa[p],ffp=fa[fp];

        	if(ffp!=g&&fp!=0)

        	{

            	if(dir(fp)==dir(p)) rot(fp);

       	     	else rot(p);

        	}

        	rot(p);

        }

    	if(g==0) root=p;

    }

    void find(int x)

    {

    	int u=root;

    	if(root==0) return ;

    	while(son[u][x>num[u]]&&x!=num[u])

    	    u=son[u][x>num[u]];

    	splay(u,0);

    }

    int pre(int x)

    {

    	find(x);

    	if(num[root]<x) return root;

    	int u=son[root][0];

    	while(son[u][1]) u=son[u][1];

    	return u;

    }

    int suc(int x)

    {

    	find(x);

    	if(num[root]>x) return root;

    	int u=son[root][1];

    	while(son[u][0]) u=son[u][0];

    	return u;

    }

    void insert(int x)

    {

    	int u=root,fu=0;

    	while(u&&x!=num[u])

    	{

    	    fu=u;

    	    u=son[u][x>num[u]];

    	}

    	if(num[u]==x) ++tot[u];

    	else

    	{

    	    u=++cnt;

    	    if(fu) son[fu][x>num[fu]]=u;

    	    siz[u]=tot[u]=1;

    	    fa[u]=fu,num[u]=x;

    	}

    	splay(u,0);

    }

    void remove(int x)

    {

    	int lst=pre(x),nex=suc(x);

    	splay(lst,0);

    	if(nex!=lst)

            splay(nex,lst);

    	int del=son[nex][0];

    	if(tot[del]>1)

    	    --tot[del],splay(del,0);

    	else son[nex][0]=0;

    }

    int rk(int x)

    {

    	find(x);

    	if(num[root]<x) return siz[root]-siz[son[root][1]];

    	return siz[son[root][0]];

    }

    int kth(int k)

    {

    	int u=root;

    	while(1)

    	{

        	if(son[u][0]&&k<=siz[son[u][0]])

        	    u=son[u][0];

        	else if(k>siz[son[u][0]]+tot[u])

        	    k-=siz[son[u][0]]+tot[u],u=son[u][1];

        	else return num[u];

    	}

    }

}sp[1000001];

int a[1000010];

int ans=0;

void build(int l,int r,int t)

{

    for(int i=l;i<=r;++i)

        sp[t].insert(a[i]);

    if(l==r) return ;

    int mid=(l+r)>>1;

    build(l,mid,t<<1);

    build(mid+1,r,t<<1|1);

}

int ll,rr;

int tree_rank(int l,int r,int t,int x)

{

    if(ll<=l&&r<=rr)

        return sp[t].rk(x)-1;

    int mid=(l+r)>>1;

    if(rr<=mid) return tree_rank(l,mid,t<<1,x);

    if(ll>mid) return  tree_rank(mid+1,r,t<<1|1,x);

    return tree_rank(l,mid,t<<1,x)+tree_rank(mid+1,r,t<<1|1,x);

}

int tree_kth(int k)

{

    int l=0,r=100000000;

    while(l<=r)

    {

        int mid=(l+r)>>1;

        int ans=tree_rank(1,n,1,mid)+1;

        if(ans<=k) l=mid+1;

        else r=mid-1;

    }

    return r;

}

void change(int l,int r,int t,int p,int pre,int nu)

{

    sp[t].remove(pre),sp[t].insert(nu);

    if(l==r) return ;

    int mid=(l+r)>>1;

    if(p<=mid)change(l,mid,t<<1,p,pre,nu);

    else change(mid+1,r,t<<1|1,p,pre,nu);

}

int tree_pre(int l,int r,int t,int x)

{

    if(ll<=l&&r<=rr)

        return ans=max(ans,num[sp[t].pre(x)]);

    int mid=(l+r)>>1;

    if(ans==x-1) return ans;

    if(rr<=mid) return ans=max(ans,tree_pre(l,mid,t<<1,x));

    if(ll>mid) return ans=max(ans,tree_pre(mid+1,r,t<<1|1,x));

    return ans=max(ans,max(tree_pre(l,mid,t<<1,x),tree_pre(mid+1,r,t<<1|1,x)));

}

int tree_suc(int l,int r,int t,int x)

{

    if(ll<=l&&r<=rr)

        return ans=min(num[sp[t].suc(x)],ans);

    int mid=(l+r)>>1;

    if(rr<=mid) return ans=min(ans,tree_suc(l,mid,t<<1,x));

    if(ll>mid) return ans=min(ans,tree_suc(mid+1,r,t<<1|1,x));

    return ans=min(min(tree_suc(l,mid,t<<1,x),tree_suc(mid+1,r,t<<1|1,x)),ans);

}

int main()

{

    //freopen("2.in","r",stdin);

    num[0]=-1;

    n=read(),m=read();

    for(int i=1;i<=n;++i)

        a[i]=read();

    /*for(int i=1;i<=n*20;++i)

        sp[i].insert(-2147483647),sp[i].insert(2147483647);*/

    build(1,n,1);

    int opt,x,y,z;

    for(int _=1;_<=m;++_)

    {

        opt=read();

        switch(opt)

        {

            case 1:

            ll=read(),rr=read(),z=read();

            printf("%d\n",tree_rank(1,n,1,z)+1);break;

            case 2:

            ll=read(),rr=read(),z=read();

            printf("%d\n",tree_kth(z));break;

            case 3:

            x=read(),y=read();

            change(1,n,1,x,a[x],y),a[x]=y;break;

            case 4:

            ans=-2147483647;

            ll=read(),rr=read(),z=read();

            printf("%d\n",tree_pre(1,n,1,z));break;

            case 5:

            ans=2147483647;

            ll=read(),rr=read(),z=read();

            printf("%d\n",tree_suc(1,n,1,z));break;

        }

    }

    return 0;

}

巴特西

洛谷 P3380 【【模板】二逼平衡树（树套树）】

完结撒花~

最新文章

热门文章