TWIST - Twist and whirl - want to cheat

no tags 

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/twist


Một tay lừa đảo có tiếng l*** đã sáng tạo ra một phương pháp để lừa bịp mọi người. Có N cái bát úp thành 1 hàng ngang trên bàn, và ở dưới mỗi cái bát đều có một quả bóng nhỏ. Các quả bóng này được đánh số từ 1 đến N từ trái sang phải. Một thao tác của l*** sẽ làm đảo ngược thứ tự của một dãy bát liên tiếp, ví dụ 2,3,4,5 thành 5,4,3,2. Sau khi l*** thực hiện M thao tác như vậy, bạn cần phải tìm ra số hiệu của N quả bóng nằm dưới N cái bát theo thứ tự từ trái sang phải.

Input
Dòng đầu chứa 2 số nguyên N và M (1<=N<=100000, 1<=M<=100000). Mỗi dòng trong M dòng tiếp theo chứa 2 số nguyên Pi, Qi (1<=Pi<=Qi<=N) - vị trí của cái bát trái nhất và phải nhất trong dãy bát liên tiếp bị đảo ngược.

Output
In ra N số nguyên trên 1 dòng thể hiện số hiệu của N quả bóng theo thứ tự từ trái sang phải.

Sample test(s)

Input
Test #1
5 2
1 3
4 5

Test #2
5 2
1 4
2 5

Output
Test #1
3 2 1 5 4

Test #2 D
4 5 1 2 3

Lưu ý: Thuật toán trâu bò sẽ bị TLE. Have fun! :D


hide comments
changyouren: 2021-10-04 03:58:32

implicit Treap


Added by:Race with time
Date:2010-11-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:NEERC Southern Subregion 2003 - 2004