BZOJ 5063 旅游

题目大意：

给你一个1~N的排列，执行M次操作。每次操作形如：

1. 从序列开头（左端）取出A个数（此时序列剩下n-A个数）
2. 从序列开头取出B个数
3. 将第1步取出的A个数按原顺序放回序列开头
4. 从序列开头取出C个数
5. 将第2步取出的B个数逆序放回序列开头
6. 将第4步取出的C个数按原顺序放回序列开头

这道题首先有反转操作，如果有这种操作基本上就Splay无疑了。

重点是：如何进行如上操作?

模拟？显然发现有的操作没必要存在，只是抽出来，放回去之类的。

所以这题的操作可以简化成：取出A+1~A+B这些数，放在新数列C和C+1中间，插入时逆序插入。

Splay维护一下就可以了。

这题我反转的时候直接赋值rev[]=1……然后GG

#include <cstdio>
#include <algorithm>
using namespace std;
  
#define N 100010
  
int n,m,ia,ib,ic,c[2][N],fa[N],rt,siz[N];
bool rev[N];
  
inline void pushup(int pos) {siz[pos]=siz[c[0][pos]]+siz[c[1][pos]]+1;}
  
inline void pushdown(int pos)
{
    if(rev[pos])
    {
        swap(c[0][c[0][pos]],c[1][c[0][pos]]);
        swap(c[0][c[1][pos]],c[1][c[1][pos]]);
        rev[c[0][pos]]^=1,rev[c[1][pos]]^=1;
        rev[pos]=0;
    }
}
  
void DFS(int pos)
{
    pushdown(pos);
    if(c[0][pos]) DFS(c[0][pos]);
    if(pos!=1&&pos!=n+2) printf("%d ",pos-1);
    if(c[1][pos]) DFS(c[1][pos]);
}
  
int build(int l,int r)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    c[0][mid]=build(l,mid-1),fa[c[0][mid]]=mid;
    c[1][mid]=build(mid+1,r),fa[c[1][mid]]=mid;
    pushup(mid);
    return mid;
}
  
void rotate(int &tg,int tx)
{
    int ty=fa[tx],tz=fa[ty],tl=(c[1][ty]==tx),tr=tl^1;
    if(ty==tg) tg=tx;
    else c[c[1][tz]==ty][tz]=tx;
    fa[tx]=tz,fa[ty]=tx;
    fa[c[tr][tx]]=ty,c[tl][ty]=c[tr][tx],c[tr][tx]=ty;
    pushup(ty),pushup(tx);
}
  
void splay(int &tg,int tx)
{
    while(tg!=tx)
    {
        int ty=fa[tx],tz=fa[ty];
        if(ty!=tg)
        {
            if((c[0][ty]==tx)^(c[0][tz]==ty)) rotate(tg,tx);
            else rotate(tg,ty);
        }
        rotate(tg,tx);
    }
}
  
int lookfor(int pos,int tg)
{
    pushdown(pos);
    if(tg<=siz[c[0][pos]]) return lookfor(c[0][pos],tg);
    if(tg>siz[c[0][pos]]+1) return lookfor(c[1][pos],tg-siz[c[0][pos]]-1);
    return pos;
}
  
int main()
{
    scanf("%d%d",&n,&m);
    rt=build(1,n+2);
    while(m--)
    {
        scanf("%d%d%d",&ia,&ib,&ic);
        splay(rt,lookfor(rt,ia+1)),splay(c[1][rt],lookfor(rt,ia+ib+2));
        ia=c[0][c[1][rt]],c[0][c[1][rt]]=0,pushup(c[1][rt]),pushup(rt);
        swap(c[0][ia],c[1][ia]),rev[ia]^=1;
        splay(rt,lookfor(rt,ic+1)),splay(c[1][rt],lookfor(rt,ic+2));
        c[0][c[1][rt]]=ia,fa[ia]=c[1][rt],pushup(c[1][rt]),pushup(rt);
    }
    DFS(rt);
    return 0;
}