TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

96.4% (53/55)

Submission's AC Ratio

47.9% (116/242)

Tags

Description

有一個由1~N的數字排成的序列。

可是你對於現在這個排列很不滿意,決定透過一些操作改變這個序列。

你現在有兩種操作:

  1. REV L R

把L到R所有數字反轉順序,例如1 2 3 4變成4 3 2 1

  1. SWAP L1 R1 L2 R2

把L1到R1所有數字跟L2到R2所有數字交換位置,但順序不變。

你總共進行了M次操作,請輸出最後序列的樣子。

Input Format

每個檔案僅含單筆測資。

第一行有兩個數字N, M,表示這個序列大小為N且初始為1~N的遞增排列、接下來會有M個操作。

接下來M行每行都是下列兩個格式之一

REV a b
SWAP a b c d

且保證1 <= a <= b < c <= d <= N

N <= 130,000
M <= 20,000

Output Format

輸出僅含一行,包含N個數字表示這個序列最後的樣子。

任兩個數字間以一個空白分開。

Sample Input 1

7 2
REV 1 4
SWAP 1 2 5 7

Sample Output 1

5 6 7 2 1 4 3

Hints

1 2 3 4 5 6 7
4 3 2 1 5 6 7
5 6 7 2 1 4 3

Problem Source

原TIOJ1633 / Problem Setter: ATP

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5