#P3391. 文艺平衡树

文艺平衡树

文艺平衡树

题目描述

给定一个长度为 nn 的整数序列,初始时序列为 {1,2,…,n−1,n}\{1,2,\dots,n-1,n\}。

序列中的位置从左到右依次标号为 1∼n1 \sim n。

我们用 [l,r][l,r] 来表示从位置 ll 到位置 rr 之间(包括两端点)的所有数字构成的子序列。

现在要对该序列进行 mm 次操作,每次操作选定一个子序列 [l,r][l,r],并将该子序列中的所有数字进行翻转。

例如,对于现有序列 1 3 2 4 6 5 7,如果某次操作选定翻转子序列为 [3,6][3,6],那么经过这次操作后序列变为 1 3 5 6 4 2 7。

请你求出经过 mm 次操作后的序列。

输入格式

第一行包含两个整数 n,mn,m。

接下来 mm 行,每行包含两个整数 l,rl,r,用来描述一次操作。

输出格式

共一行,输出经过 mm 次操作后的序列。

输入样例

6 3
2 4
1 5
3 5

输出样例

5 2 1 4 3 6

数据范围

  • 1≤n,m≤1051 \le n, m \le 10^5
  • 1≤l≤r≤n1 \le l \le r \le n

来源

模板题 AcWing / 洛谷 P3391 难度:中等 时/空限制:1s / 64MB