Loading...

洛谷P3391 文艺平衡树

check评论:0 条 remove_red_eye浏览量:569 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-16

区间翻转裸题

我们要翻转的时候就给这个点打标记,之后$pushdown$的时候直接交换左右子树救星

其他的就是$splay$基本操作啦

#include <bits/stdc++.h>
using namespace std;
int f[100010],ch[100010][2],key[100010],cnt[100010],siz[100010],tag[100010];
int sz,root,n,m;
void clear(int x)
{
    f[x]=ch[x][0]=ch[x][1]=cnt[x]=siz[x]=key[x]=0;
} 
void update(int x)
{
    if(x)
    {
        siz[x]=cnt[x];
        if(ch[x][0])
        {
            siz[x]+=siz[ch[x][0]];
        }
        if(ch[x][1])
        {
            siz[x]+=siz[ch[x][1]];
        }
    }
}
int get(int x)
{
    return ch[f[x]][1]==x;
}
void rotate(int x)
{
    int old=f[x],oldf=f[old],which=get(x);
    ch[old][which]=ch[x][which^1];
    f[ch[old][which]]=old;
    ch[x][which^1]=old;
    f[old]=x;
    f[x]=oldf;
    if(oldf)
    {
        ch[oldf][old==ch[oldf][1]]=x;
    }
    update(old);
    update(x);
}
void splay(int x,int goal=0)
{
    for(int fa;fa=f[x],fa!=goal;rotate(x))
    {
        if(f[fa]!=goal)
        {
            rotate(get(x)==get(fa)?fa:x);
        }
    }
    if(!goal)
    {
        root=x;
    }
}
void ins(int x)
{
    if(root==0)
    {
        sz++;
        clear(sz);
        cnt[sz]=siz[sz]=1;
        key[sz]=x;
        root=sz;
        return ;
    }
    int now=root,fa=0;
    while(1)
    {
        if(key[now]==x)
        {
            cnt[now]++;
            update(now);
            update(fa);
            splay(now);
            return ;
        }
        fa=now;
        now=ch[now][key[now]<x];
        if(now==0)
        {
            sz++;
            clear(sz);
            cnt[sz]=siz[sz]=1;
            key[sz]=x;
            f[sz]=fa;
            ch[fa][key[fa]<x]=sz;
            update(fa);
            splay(sz);
            return ;
        }
    }
}
void pushdown(int x)
{
    if(tag[x])
    {
        swap(ch[x][0],ch[x][1]);
        tag[ch[x][0]]^=1;
        tag[ch[x][1]]^=1;
        tag[x]=0;
    }
}
int kth(int x)
{
    int now=root;
    while(1)
    {
        pushdown(now);
        if(ch[now][0]&&x<=siz[ch[now][0]])
        {
            now=ch[now][0];
            continue;
        }
        int rank=(ch[now][0]?siz[ch[now][0]]:0)+cnt[now];
        if(x<=rank)
        {
            return now;
        }
        x-=rank;
        now=ch[now][1];
    }
}
void rev(int l,int r)
{
    int k1=kth(l);
    int k2=kth(r+2);
    splay(k1,0);
    splay(k2,k1);
    tag[ch[ch[root][1]][0]]^=1;
}
void output(int now)
{
    pushdown(now);
    if(ch[now][0])
    {
        output(ch[now][0]);
    }
    if(key[now]>1&&key[now]<n+2)
    {
        printf("%d ",key[now]-1);
    }
    if(ch[now][1])
    {
        output(ch[now][1]);
    }
} 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n+2;i++)
    {
        ins(i);
    }
    for(int i=1;i<=m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        rev(l,r);
    }
    output(root);
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名