/ FtOJ / 题库 /

「模板」文艺平衡树

「模板」文艺平衡树

Description

您需要写一种数据结构(可参考题目标题),来维护一个序列,其中需要提供以下操作:

翻转一个区间,例如原有序序列是 5 4 3 2 1,翻转区间是 \([2,4]\) 的话,结果是 5 2 3 4 1

Format

Input

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

接下来 \(m\) 行每行两个数 \([l,r]\),数据保证 \(1 \le l \le r \le n\)。

Output

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

Sample 1

Input

5 3
1 3
1 3
1 4

Output

4 3 2 1 5

Limitation

Data

\(1 \le n,m \le 10^5\)

Time and Space

1s, 125MB.

Source

loj #105

update by Shuchong

信息

ID
1005
难度
(无)
分类
平衡树 点击显示
标签
递交数
24
已通过
13
通过率
54%
上传者

相关

在下列训练计划中:

熟悉环境

试炼场

在以下作业中:

窝只系熟悉一下qwq (by TNT_C6H2CH3(NO2)3)