求助splay板子,代码通俗易懂
查看原帖
求助splay板子,代码通俗易懂
85682
绝顶我为峰kkksd06楼主2020/7/21 21:23

RT,在板子题上去世了,求大佬挑错,谢谢大家(鞠躬)

#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int n,m,tot,rt,fa[100005],ch[100005][2],cnt[100005],val[100005],sz[100005],tag[100005][2],maxn[100005],a[100005];
inline void maintain(int x)
{
    sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
    maxn[x]=max(val[x],max(maxn[ch[x][0]],maxn[ch[x][1]]));
}
inline bool get(int x)
{
    return x==ch[fa[x]][1];
}
inline void push_down(int x)
{
    if(ch[x][0])
    {
        val[ch[x][0]]+=tag[x][0];
        tag[ch[x][0]][0]+=tag[x][0];
        maxn[ch[x][0]]+=tag[x][0];
    }
    if(ch[x][1])
    {
        val[ch[x][1]]+tag[x][0];
        tag[ch[x][1]][0]+=tag[x][0];
        maxn[ch[x][1]]+=tag[x][0];
    }
    if(tag[x][1])
    {
        ch[x][0]^=ch[x][1]^=ch[x][0]^=ch[x][1];
        tag[ch[x][0]][1]^=1;
        tag[ch[x][1]][1]^=1;
    }
    tag[x][0]=tag[x][1]=0;
}
inline void rotate(int x)
{
    int y=fa[x],z=fa[y];
    push_down(y);
    push_down(x);
    int k=get(x);
    ch[y][k]=ch[x][k^1];
    fa[ch[x][k^1]]=y;
    ch[x][k^1]=y;
    fa[y]=x;
    fa[x]=z;
    if(z)
        ch[z][y==ch[z][1]]=x;
    maintain(y);
    maintain(x);
}
inline void splay(int x,int goal)
{
    for(register int f=fa[x];(f=fa[x])!=goal;rotate(x))
        if(fa[f]!=goal)
            rotate(get(f)==get(x)? f:x);
    if(!goal)
        rt=x;
}
inline int build(int f,int l,int r)
{
    if(l>r)
        return 0;
    int node=++tot,mid=(l+r)>>1;
    fa[node]=f;
    val[node]=maxn[node]=a[mid];
    cnt[node]=1;
    ch[node][0]=build(node,l,mid-1);
    ch[node][1]=build(node,mid+1,r);
    maintain(node);
    return node;
}
inline int kth(int k)
{
    int node=rt;
    while(1)
    {
        push_down(node);
        if(ch[node][0]&&k<=sz[ch[node][0]])
            node=ch[node][0];
        else
        {
            k-=cnt[node]+sz[ch[node][0]];
            if(k<=0)
                return node;
            node=ch[node][1];
        }
    }
}
inline void update(int l,int r,int k)
{
    l=kth(l-1);
    r=kth(r+1);
    splay(l,0);
    splay(r,l);
    tag[ch[ch[rt][1]][0]][0]+=k;
    val[ch[ch[rt][1]][0]]+=k;
    maxn[ch[ch[rt][1]][0]]+=k;
}
inline void reverse(int l,int r)
{
    l=kth(l-1);
    r=kth(r+1);
    splay(l,0);
    splay(r,l);
    tag[ch[ch[rt][1]][0]][1]^=1;
}
int query(int l,int r)
{
    l=kth(l-1);
    r=kth(r+1);
    splay(l,0);
    splay(r,l);
    return maxn[ch[ch[rt][1]][0]];
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    maxn[0]=a[1]=a[n+2]=-1<<30;
    rt=build(0,1,n+2);
    while(m--)
    {
        int opt,x,y;
        scanf("%lld%lld%lld",&opt,&x,&y);
        if(opt==1)
        {
            int k;
            scanf("%lld",&k);
            update(x+1,y+1,k);
        }
        if(opt==2)
            reverse(x+1,y+1);
        if(opt==3)
            printf("%lld\n",query(x+1,y+1));
    }
    return 0;
}
2020/7/21 21:23
加载中...