简单splay模板

2024-05-29 03:18

文章标签 简单模板 splay

本文主要是介绍简单splay模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

splay(x,y)表示将点x旋转到y的下面
fa[x]表示点x的父亲
t[x][0/1]表示点x的左/右儿子
updata用来维护需要维护的东西
标程均为求最大值

单点修改

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 101000
using namespace std;
int n,a[N],b[N],fa[N],t[N][2];
void updata(int x){a[x]=max(b[x],max(a[t[x][0]],a[t[x][1]]));}
bool lr(int x){return x==t[fa[x]][1];}
void rotate(int x)
{
    int k=lr(x),y=fa[x];
    t[y][k]=t[x][1-k];
    if(t[x][1-k]) fa[t[x][1-k]]=y;
    fa[x]=fa[y];
    if(fa[y]) t[fa[y]][lr(y)]=x;
    t[x][1-k]=y;fa[y]=x;
    updata(y);updata(x);
}
void splay(int x,int y)
{
    while(fa[x]!=y)
    {
        if(fa[fa[x]]!=y)
            if(lr(fa[x])==lr(x)) rotate(fa[x]);
            else rotate(x);
        rotate(x);
    }
}
int main()
{
    scanf("%d",&n);
    fo(i,1,n)
    {
        scanf("%d",&b[i+1]);
        fa[i]=i+1;t[i+1][0]=i;updata(i+1);
    }
    fa[n+1]=n+2;t[n+2][0]=n+1;updata(n+2);
    int m;
    for(scanf("%d",&m);m;m--)
    {
        int x,y,z;scanf("%d%d%d",&z,&x,&y);x++;
        if(z==1)
        {
            splay(x,0);b[x]=y;updata(x);
        }
        else
        {
            y++;splay(x-1,0);
            splay(y+1,x-1);printf("%d\n",a[t[y+1][0]]);
        }
    }
}

区间修改

lz为懒标记
xc和down为下传

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 101000
using namespace std;
int a[N],t[N][2],fa[N],lz[N],b[N],n,s[N];
int lr(int x){return x==t[fa[x]][1];}
void updata(int x){a[x]=max(b[x],max(a[t[x][0]],a[t[x][1]]));}
void down(int x,int v)
{
    a[x]+=v;lz[x]+=v;b[x]+=v;
}
void xc(int x,int y)
{
    while(x!=y){s[++s[0]]=x;x=fa[x];}
    for(;s[0];s[0]--)
    {
        int z=s[s[0]];
        if(lz[z])
        {
            if(t[z][0]) down(t[z][0],lz[z]);
            if(t[z][1]) down(t[z][1],lz[z]);
        }
        lz[z]=0;
    }
}
void rotate(int x)
{
    int k=lr(x),y=fa[x];
    t[y][k]=t[x][1-k];if(t[x][1-k]) fa[t[x][1-k]]=y;
    fa[x]=fa[y];if(fa[y]) t[fa[y]][lr(y)]=x;
    t[x][1-k]=y;fa[y]=x;
    updata(y);updata(x);
}
void splay(int x,int y)
{
    xc(x,y);
    while(fa[x]!=y)
    {
        if(fa[fa[x]]!=y)
            if(lr(x)==lr(fa[x])) rotate(fa[x]);
            else rotate(x);
        rotate(x);
    }
}
int main()
{
    freopen("splay.in","r",stdin);
    freopen("splay.out","w",stdout);
    scanf("%d",&n);
    memset(a,-127,sizeof(a));
    fo(i,1,n)
    {
        fa[i]=i+1;t[i+1][0]=i;
        scanf("%d",&b[i+1]);updata(i+1);
    }
    fa[n+1]=n+2;t[n+2][0]=n+1;updata(n+2);
    int ac;
    for(scanf("%d",&ac);ac;ac--)
    {
        int x,y,z;scanf("%d%d%d",&z,&x,&y);x++;y++;
        splay(x-1,0);splay(y+1,x-1);
        if(z==1)
        {
            int add;scanf("%d",&add);
            down(t[y+1][0],add);
        }
        else printf("%d\n",a[t[y+1][0]]);
    }
}