P3391 【模板】文艺平衡树[splay]

目背景

题目描述

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

输入输出格式

输入格式:

第一行为 $ n ,m$ $n$ 表示初始序列有 $n$ 个数,这个序列依次是 $(1,2, \cdots n-1,n)$ $m$表示翻转操作次数

接下来m行每行两个数 $[l,r]$ 数据保证 $1 \leq l \leq r \leq n$

输出格式:

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

输入输出样例

输入样例#1:

1
2
3
4
5 3
1 3
1 3
1 4

输出样例#1:

1
4 3 2 1 5

说明

$n, m \leq 100000$

题解

模板题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
inline int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
const int maxn=1e5+100;
int fa[maxn],ch[maxn][2],rev[maxn],sz[maxn];
int n,M,X,Y,rt;
inline void maintain(int x) {sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;}
inline void pushdown(int x)//把翻转标记往下传
{
if (rev[x])
{
swap(ch[x][0],ch[x][1]);
rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;rev[x]=0;
}
}
inline void bt(int &d,int l,int r)
{
if (r<l) return;
int mid=(l+r)>>1;
if (mid<d) ch[d][0]=mid; else ch[d][1]=mid;
fa[mid]=d;sz[mid]=1;rev[mid]=0;
if (l==r) return;
bt(mid,l,mid-1);bt(mid,mid+1,r);
maintain(mid);
}
inline int Kth(int &d,int k)//求第k大
{
pushdown(d);
if (sz[ch[d][0]]==k-1) return d;
if (sz[ch[d][0]]>=k) return Kth(ch[d][0],k);
return Kth(ch[d][1],k-sz[ch[d][0]]-1);
}
inline void rotate(int &d)//把d旋到fa[d]位置
{//各种标记,具体见treap模板
int k= ch[fa[d]][1]==d;
int y=fa[d];int ft=fa[y];
ch[y][k]=ch[d][k^1];
fa[ch[d][k^1]]=y;
ch[d][k^1]=y;
ch[ft][ch[ft][1]==y]=d;
fa[d]=ft;fa[y]=d;
maintain(y);maintain(d);
}
inline void splay(int x,int &root)
{
int ft=fa[root];
while (fa[x]!=ft)//翻转到根
{
if (fa[x]!=root) ((ch[fa[x]][1]==x)^(ch[fa[fa[x]]][1]==fa[x])) ? rotate(x) : rotate(fa[x]);
rotate(x);
}
if (ft==0) rt=x;
}
void write(int x)//输出
{
if (x==0) return;
pushdown(x);
write(ch[x][0]);
if (x>1&&x<n+2) printf("%d ",x-1);
write(ch[x][1]);
}

int main()
{
n=read();M=read();
rt=(3+n)>>1;fa[rt]=0;
bt(rt,1,rt-1);bt(rt,rt+1,n+2);
while (M--)
{
X=read();Y=read();//X,Y+2
int x=Kth(rt,X);
int YY=Kth(rt,Y+2);
splay(x,rt);//return 0;
splay(YY,ch[rt][1]);
rev[ch[ch[rt][1]][0]]^=1;
}
write(rt);
return 0;
}