1. 题目

传送门= ̄ω ̄=

题目大意:

给你一个长度为$n$的序列,还有$m$个操作,每次操作给出区间$[l,r]$,表示将该区间内的数字反转(比如123变成321),求所有操作后的序列。

$n,m<=100000$

2. 题解

裸的splay区间操作(反转),拿来练手,毕竟很久没打splay了。

splay的区间操作的话,比如操作$[l,r]$,只要把$l-1$所对应的节点splay到根,然后再把$r+1$对应的节点splay到根的右儿子,那么区间$[l,r]$所对应的所有节点就都在$r+1$的左儿子为根的子树里了,给$r+1$的左儿子打上标记即可。

由于$l-1$和$r+1$可能为$0$或$n+1$,所以我们加入两个没用的节点放在$0$和$n+1$这两个位置,输出答案的时候注意要判断不为这两个节点再输出。

代码:

#include <bits/stdc++.h>
#define NS (100005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,data[NS],sz,root;
struct N{int s[2],f,d,m,sz;}e[NS];
void pup(int a){e[a].sz=e[e[a].s[0]].sz+e[e[a].s[1]].sz+1;}
void pdown(int a)
{
    if(!e[a].m)return;
    e[e[a].s[0]].m^=1,e[e[a].s[1]].m^=1;
    swap(e[a].s[0],e[a].s[1]),e[a].m=0;
}
int build(int fa,int l,int r)
{
    if(l>r)return 0;
    int mid=(l+r)>>1,pos=++sz;
    e[pos].d=data[mid],e[pos].f=fa;
    e[pos].s[0]=build(pos,l,mid-1);
    e[pos].s[1]=build(pos,mid+1,r);
    pup(pos);
    return pos;
}
int jud(int a){return e[e[a].f].s[1]==a;}
void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=jud(a),q=jud(f);
    pdown(f),pdown(a);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
    pup(f),pup(a);
}
void splay(int a,int t)
{
    while(e[a].f!=t)
    {
        if(e[e[a].f].f!=t)
        {
            if(jud(a)^jud(e[a].f))rot(a);
            else rot(e[a].f);
        }
        rot(a);
    }
    if(!t)root=a;
}
int find_by_order(int x)
{
    int a=root;
    while(a)
    {
        pdown(a);
        if(x<=e[e[a].s[0]].sz)a=e[a].s[0];
        else
        {
            x-=e[e[a].s[0]].sz+1;
            if(!x)return a;
            a=e[a].s[1];
        }
    }
    return 0;
}
void pans(int a)
{
    pdown(a);
    if(e[a].s[0])pans(e[a].s[0]);
    if(e[a].d!=-1e8&&e[a].d!=1e8)printf("%d ",e[a].d);
    if(e[a].s[1])pans(e[a].s[1]);
}
int main()
{
    IN(n),IN(m);
    for(int i=1;i<=n;i++)data[i+1]=i;
    data[1]=-1e8,data[n+2]=1e8,root=build(0,1,n+2);
    for(int i=1,l,r;i<=m;i++)
    {
        IN(l),IN(r),l=find_by_order(l),r=find_by_order(r+2);
        splay(l,0),splay(r,l);
        e[e[e[root].s[1]].s[0]].m^=1;
    }
    pans(root);
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

1 条评论

【题解】 序列终结者 splay BZOJ – 1251 | K-XZY · 2017年12月18日 1:30 下午

[…] splay的区间操作可以参见这篇文章:传送门= ̄ω ̄= […]

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *