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$这两个位置,输出答案的时候注意要判断不为这两个节点再输出。

代码: