同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1580_文艺平衡树

2022-5-16 18:17| 发布者: Hocassian| 查看: 54| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-89503991554000-Problem List-采集的数据-后羿采集器.html

Pro.ID

1580

Title

文艺平衡树

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1580

AC

Submit

Ratio

37.50%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)

描述

这是一道模板题。

您需要写一种数据结构（可参考题目标题），来维护一个序列，其中需要提供以下操作：

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

输入

多测试用例。

每个测试用例第一行为 n, m（ 1 ≤ n, m ≤ 10⁵ ）， n 表示初始序列有 n 个数，这个序列依次是 {1, 2, … n-1, n} ，m 表示翻转操作次数。

接下来 m 行每行两个数 [l, r] ，数据保证 1 ≤ l ≤ r ≤ n 。

输出

Description

这是一道模板题。

您需要写一种数据结构（可参考题目标题），来维护一个序列，其中需要提供以下操作：

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

Input

多测试用例。

每个测试用例第一行为 n, m（ 1 ≤ n, m ≤ 10⁵ ）， n 表示初始序列有 n 个数，这个序列依次是 {1, 2, … n-1, n} ，m 表示翻转操作次数。

接下来 m 行每行两个数 [l, r] ，数据保证 1 ≤ l ≤ r ≤ n 。

Output

每个测试用例输出一行 n 个数字，表示原始序列经过 m 次变换后的结果。

Sample Input

5 3
1 3
1 3
1 4

Sample Output

4 3 2 1 5

Author

John

样例输入