33OJ
登录 注册

#A0069. 【模板】文艺平衡树

    ID: 94 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>数据结构平衡树O2优化

【模板】文艺平衡树

Problem Description

You need to implement a data structure (you can refer to the title) to maintain an ordered sequence.

It must support the following operation: reverse a segment. For example, if the original ordered sequence is 5 4 3 2 15\ 4\ 3\ 2\ 1, and the reversed segment is [2,4][2, 4], then the result is 5 2 3 4 15\ 2\ 3\ 4\ 1.

Input Format

The first line contains two positive integers n,mn, m, denoting the length of the sequence and the number of operations. Initially, the ii-th element of the sequence is ii.

Then follow mm lines, each containing two positive integers l,rl, r, denoting the segment to reverse.

Output Format

Output one line with nn positive integers, which is the result after applying mm reversals to the original sequence.

5 3
1 3
1 3
1 4
4 3 2 1 5

Hint

Constraints
For 100%100\% of the testdata, 1≤n,m≤1000001 \le n, m \le 100000, 1≤l≤r≤n1 \le l \le r \le n.

Translated by ChatGPT 5