1419 . 巨砲編輯器
TopCoder
Tags
Description
小奕有一個文字編輯器，在他的檔案裡面有 $n$ 個整數，依序是 $a_1, a_2, \ldots, a_n$。
為了展現他電腦的強大運算能力，小奕每次會選定一個區間 $[l, r]$，以及兩個數字 $x, y$，這代表他會框選起整個區間 $a_l, a_{l+1}, \ldots, a_{r}$，搜尋當中是 $x$ 的整數，並把他們都取代成 $y$。
因為小奕是個頂尖科技公司的軟體工程師，他會記得把「配對整個單字」的選項打開，也就是改變只有在 $a_i = x$ 才會被改成 $y$，不會發生替換 54 成 76 結果把 6547 變成 6767，或者是把 int 取代成 long long 結果把 printf 變成 prlong longf。
不過就在這個時候，小奕寫了一個腳本每秒處理上萬次操作之後，他的工作站就這樣卡住了，他很好奇如果所有指令都成功執行後，最後結果是什麼，你可以寫一隻程式計算最後的結果嗎？
Input Format
輸入的第一行有兩個整數 $n, q$，其中 $n$ 是檔案中的數字數量，而 $q$ 是小奕使用取代功能的次數。
第二行有 $n$ 個整數 $a_1, a_2, \ldots, a_n$，依序為小奕檔案中一開始的所有數字。
接下來有 $q$ 行，依序是小奕執行的取代功能參數，每一行都有四個整數 $l, r, x, y$，代表小奕將檔案中 $a_l, a_{l+1}, \ldots, a_r$ 中等於 $x$ 的數字都取代成 $y$。
- $1 \leq n, q \leq 5 \times 10 ^ 5$
- $1 \leq l \leq r \leq n$
- $1 \leq a_i, x, y \leq n$
Output Format
輸出一行 $n$ 個以空白分開的整數 $a'_1, a'_2, \ldots, a'_n$，其中 $a'_i$ 代表 $a_i$ 經過這 $q$ 次取代操作之後的結果。
Sample Input 1
5 4 1 2 3 3 5 4 5 3 4 1 5 2 5 3 3 3 2 1 2 2 4
Sample Output 1
1 5 2 4 5
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資。 | 0 |
| 2 | 0~10 | $a_i, x, y \leq 16$ | 35 |
| 3 | 0~26 | 無特別限制。 | 65 |