TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

89.5% (17/19)

Submission's AC Ratio

55.4% (51/92)

Tags

CF

Description

解決完印尼巨港市面臨的難題的小向,坐在辦公室裡,身體靠著椅背,稍微休息了一下。沒想到小向突然就被吸回了原本的時空,

「……你成長得真快啊……」
「師父?」

待小向回過神來,她已經站在森林的正中心。在她面前的是一個巨大的牢籠,以及一個被關在裡面的人。

「希爾伯特……希爾伯特是你嗎?」
「小向……終於來到這裡啦…」
「你等一下,我馬上把你放出來。」

小向拉了一下門,不過想也知道籠子是鎖的。小向想起了她對付茶葉…噢不,是烏龍,時所用的破壞系咒語。
「霹麗卡霹麗拉拉,波波麗那貝貝魯多!」
小向的魔杖發出了強大的光芒,緊接著是一陣煙霧。不過煙霧消散後,牢籠仍沒被破壞。
「哎呀…原來你還會這種魔法啊…不過沒用的,這個牢籠封印了魔法,而且不受外界魔力影響。要不然我早就逃脫了。」
說得也是呢…

「說也好笑,這牢籠是我打造的。竟然被自己的打造的東西關住,我也真是沒用的。不過嘛…因為是我製造的,所以我還記得流程呢…甚至是開啟這牢籠的鑰匙我也記得…」
「真的嗎?可以告訴我詳細的過程嗎?」小向如此追問。
「可以是可以…不過為什麼要呢?」
「只要知道原料以及流程,就可以推算出最後的分子排列方法,我就可以造出一把鑰匙了。」

「這樣啊…好吧!我就告訴你吧!

鑰匙的原料是一個長條狀的物體,大致可分成$N$小塊。每塊的分子狀態可以由一個英文小寫字母表示。在鍛造的時候,每當我敲一次鑰匙,會有其中一段區間的分子狀態重新排列:可能是排成由小排到大的排列,也有可能是由大排到小,……」

接著希爾伯特把原料的狀態以及之後分子排列變化過程告訴了小向,而聰明的小向當然要用這些訊息推算出鑰匙的構造囉!

Input Format

第一行有兩個正整數$N\leq 10^ 5,M\leq 50000$,分別代表鑰匙的區塊數以及希爾伯特敲擊鑰匙的次數。
第二行有一個長度為$N$的字串,代表鑰匙原料的初始狀態。所有字元都是英文小寫字母。
接下來有$M$行,每行有三個整數$1\leq i\leq j\leq N, 0\leq k\leq 1$,代表這次敲擊讓第$i$個字元(含)一直到第$j$個字元(含)重新排列(編號由1編號到$N$)。如果$k=1$就代表由小排到大,$k=0$代表由大排到小。

子任務(測資) 額外限制 分數
1 (0~4) $N,M\leq 10^ 4$ 24
2 (5~9) 只有a,b兩個字元 36
3 (10~14) 40

Output Format

輸出一個長度為$N$的字串,代表鑰匙最終的狀態。

Sample Input

10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1

Sample Output

cbcaaaabdd

Hints

abacdabcda → abacdadcba → abacacddba → cbaaacddba → cbcaaaddba → cbcaaaabdd

Problem Source

Problem Set / Description by Paupière
題目取自Codeforces.

Subtasks

For Testdata: 0 ~ 4, Score: 24
For Testdata: 5 ~ 9, Score: 36
For Testdata: 10 ~ 14, Score: 40
No. Time Limit (ms) Memory Limit (KiB)
0 4000 524288
1 4000 524288
2 4000 524288
3 4000 524288
4 4000 524288
5 4000 524288
6 4000 524288
7 4000 524288
8 4000 524288
9 4000 524288
10 4000 524288
11 4000 524288
12 4000 524288
13 4000 524288
14 4000 524288