这是一道经典的Splay模板题——文艺平衡树。
您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1
输入格式:
第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2, \cdots n-1,n)(1,2,⋯n−1,n) m表示翻转操作次数
接下来m行每行两个数 [l,r][l,r] 数据保证 1 \leq l \leq r \leq n1≤l≤r≤n
输出格式:
输出一行n个数字,表示原始序列经过m次变换后的结果
输入样例#1
5 3
1 3
1 3
1 4
输出样例#1:
4 3 2 1 5
n, m \leq 100000n,m≤100000
补一发splay版
以下标建一棵树
每次按照规则旋转就好
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1e5+10;
const int maxn=0x7fffff;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
char c=nc();int x=0,f=1;
while(c<'0'||c>'9'){c=nc();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
return x*f;
}
int n,m;
struct node
{
int tot,fa,ch[2];
bool rev;
}tree[MAXN];
int tot,point;
int root;
int PosL,PosR;
inline void connect(int x,int fa,bool how)
{
tree[x].fa=fa;
tree[fa].ch[how]=x;
}
inline void update(int k)
{
tree[k].tot=tree[tree[k].ch[0]].tot+tree[tree[k].ch[1]].tot+1;
}
inline int BuildTree(int l,int r)
{
if(l>r) return 0;
int mid=(l+r)>>1;
connect(BuildTree(l,mid-1),mid,0);
connect(BuildTree(mid+1,r),mid,1);
tree[mid].rev=0;
update(mid);
return mid;
}
inline bool ident(int x)
{
return tree[tree[x].fa].ch[1]==x;
}
inline void pushdown(int x)
{
if(tree[x].rev)
{
swap(tree[x].ch[0],tree[x].ch[1]);
tree[tree[x].ch[0]].rev^=1;
tree[tree[x].ch[1]].rev^=1;
tree[x].rev=0;
}
}
inline void rotate(int X)
{
// pushdown(tree[X].fa);pushdown(X);
int Y=tree[X].fa;
if(Y==root) root=X;
int R=tree[Y].fa;
bool Yson=ident(X);
bool Rson=ident(Y);
int B=tree[X].ch[Yson^1];
connect(B,Y,Yson);
connect(Y,X,Yson^1);
connect(X,R,Rson);
update(Y);update(X);
}
inline void splay(int x,int to)
{
while(tree[x].fa!=to)
{
if(tree[tree[x].fa].fa==to) rotate(x);
else if(ident(x)==ident(tree[x].fa)) rotate(tree[x].fa),rotate(x);
else rotate(x),rotate(x);
}
update(x);
}
inline int find(int x)
{
int now=root;x--;
pushdown(now);
while(x!=tree[tree[now].ch[0]].tot)
{
if (tree[tree[now].ch[0]].tot<x) x-=tree[tree[now].ch[0]].tot+1,now=tree[now].ch[1];
else now=tree[now].ch[0];
pushdown(now);
}
return now;
}
void print(int now)
{
if(!now) return ;
pushdown(now);
print(tree[now].ch[0]);
if(now!=1&&now!=n+2) printf("%d ",now-1);
print(tree[now].ch[1]);
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
n=read(),m=read();
root=BuildTree(1,n+2);
for(int i=1;i<=m;i++)
{
int l=read(),r=read();
PosL=find(l);
splay(PosL,0);
PosR=find(r+2);
splay(PosR,root);
tree[tree[PosR].ch[0]].rev^=1;
}
print(root);
}