题目描述

Description

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

Input

第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n

Output

输出一行n个数字，表示原始序列经过m次变换后的结果

Sample Input

5 3
1 3
1 3
1 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

题目分析

splay裸题 维护标记

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> par;
int n,m;
int val[101000],lazy[101000],size[101000],key[101000],lson[101000],rson[101000];
int tot,root;
void update(int x)
{
    size[x]=size[lson[x]]+size[rson[x]]+1;
}
void pushdown(int x)
{
    if(!lazy[x]) return ;
    swap(lson[x],rson[x]),lazy[x]=0;
    if(lson[x]) lazy[lson[x]]^=1;
    if(rson[x]) lazy[rson[x]]^=1;
}
int merge(int x,int y)
{
    pushdown(x),pushdown(y);
    if(x==0||y==0) return x|y;
    if(key[x]<key[y])
    {
        lson[y]=merge(x,lson[y]),update(y);
        return y;
    }
    rson[x]=merge(rson[x],y),update(x);
    return x;
}
par split(int x,int k)
{
    pushdown(x);
    if(k==0) return make_pair(0,x);
    int l=lson[x],r=rson[x];
    if(k==size[lson[x]])
    {
        lson[x]=0,update(x);
        return make_pair(l,x);
    }
    if(k==size[lson[x]]+1)
    {
        rson[x]=0,update(x);
        return make_pair(x,r);
    }
    par t;
    if(k<size[lson[x]])
    {
        t=split(l,k);
        lson[x]=t.second,update(x);
        return make_pair(t.first,x);
    }
    else
    {
        t=split(r,k-size[lson[x]]-1);
        rson[x]=t.first,update(x);
        return make_pair(x,t.second);
    }
}
void output(int x,int flag)
{
    pushdown(x);
    if(lson[x]) output(lson[x],0);
    if(!rson[x]&&flag) printf("%d",val[x]);
    else printf("%d ",val[x]);
    if(rson[x]) output(rson[x],flag);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        key[++tot]=rand()*rand(),val[tot]=i,size[tot]=1,root=merge(root,tot);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        par t1,t2;
        t2=split(root,y),t1=split(t2.first,x-1);
        lazy[t1.second]^=1;
        root=merge(merge(t1.first,t1.second),t2.second);
    }
    output(root,1);
    return 0;
}