description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

analysis

• 我他妈终于会\(splay\)翻转板子了

• 注意翻转标记不用整条链下传，只需查找时交换儿子节点

• 注意下标和存储值是不一样的

code

#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 100005
#define INF 1000000007
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)

using namespace std;

ll tr[MAXN][2];
ll fa[MAXN],size[MAXN],val[MAXN],rev[MAXN];
ll n,m,tot,root;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void newnode(ll &x,ll y,ll z)
{
    x=++tot,tr[x][0]=tr[x][1]=0,fa[x]=z,size[x]=1,val[x]=y;
}
inline void update(ll x)
{
    size[x]=size[tr[x][0]]+size[tr[x][1]]+1;
}
inline void build(ll &x,ll l,ll r,ll y)
{
    if (l>r)return;
    ll mid=(l+r)>>1;newnode(x,mid,y);
    build(tr[x][0],l,mid-1,x),build(tr[x][1],mid+1,r,x);
    update(x);
}
inline ll lr(ll x)
{
    return tr[fa[x]][1]==x;
}
inline void rotate(ll x)
{
    ll y=fa[x],k=lr(x);
    tr[y][k]=tr[x][!k];
    if (tr[x][!k])fa[tr[x][!k]]=y;
    fa[x]=fa[y];
    if (fa[y])tr[fa[y]][lr(y)]=x;
    tr[x][!k]=y,fa[y]=x;
    update(y),update(x);
}
inline void splay(ll x,ll y)
{
    while (fa[x]!=y)
    {
        if (fa[fa[x]]!=y)
        {
            if (lr(fa[x])==lr(x))rotate(fa[x]);
            else rotate(x);
        }
        rotate(x);
    }
    if (y==0)root=x;
}
inline void down(ll x)
{
    if (rev[x])
    {
        swap(tr[x][0],tr[x][1]);
        rev[tr[x][0]]^=1,rev[tr[x][1]]^=1,rev[x]=0;
    }
}
inline ll find(ll x,ll y)
{
    down(x);
    if (y==size[tr[x][0]]+1)return x;
    if (y<=size[tr[x][0]])return find(tr[x][0],y);
    else return find(tr[x][1],y-size[tr[x][0]]-1);
}
inline void modify(ll x,ll y)
{
    ll l=find(root,x),r=find(root,y+2);
    splay(l,0),splay(r,root);
    rev[tr[r][0]]^=1;
}
int main()
{
    freopen("P3391.in","r",stdin);
    n=read(),m=read();
    newnode(root,INF,0),newnode(tr[root][1],INF,root);
    build(tr[tr[root][1]][0],1,n,tr[root][1]);
    while (m--)
    {
        ll x=read(),y=read();
        modify(x,y);
    }
    fo(i,2,n+1)printf("%lld ",val[find(root,i)]);
    return 0;
}

【BZOJ3223】【luoguP3391】文艺平衡树

原文：https://www.cnblogs.com/horizonwd/p/11279613.html