「BZOJ3223」JoyOI 1729 文艺平衡树

2014年7月22日8,47026

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 31 31 31 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

题解

4:22 *1

7:22 *1

直接splay。。。 区间翻转而已。。。

 

说点什么

提醒
avatar
autoint
autoint

学长,在一般情况下90行的rt=(n+3)>>1;是不是应改为`rt=id[(n+3)>>1];’?

苦读依旧

id数组是不是为了省空间啊

DJRAA12
DJRAA12

求问黄学长,为什么有区间翻转操作的时候,splay不需要pushdown…做这类题一直搞不懂

Sigma_Poet
Sigma_Poet

学长,你为什要建1..n + 2 区间的Splay树,而并不是1..n

will7101
will7101

帮学长回答一下。。。1和n+2是两侧的哨兵节点,这样就可以在访问2..n+1区间(左右边界)的时候提起0和n+2节点。

Sigma_Poet
Sigma_Poet

黄学长,你的SPLAY中的splay和rotate都是传的两个参数,如果现在要进行启发式合并(也就是有多棵Splay,有许多根),那么int &k那里肯定要传的是当前结点所在的Splay的根。怎么维护这个根结点啊??

Alisa
Alisa

为什么rever中是y=find(rt,r+2);?

ztc
ztc

看黄学长主页学过来的

张虎

那个find函数到底是find什么鬼

涵丶

一直不理解id数组到底是什么含义。。