解決完印尼巨港市面臨的難題的小向,坐在辦公室裡,身體靠著椅背,稍微休息了一下。沒想到小向突然就被吸回了原本的時空,
「……你成長得真快啊……」
「師父?」
待小向回過神來,她已經站在森林的正中心。在她面前的是一個巨大的牢籠,以及一個被關在裡面的人。
「希爾伯特……希爾伯特是你嗎?」
「小向……終於來到這裡啦…」
「你等一下,我馬上把你放出來。」
小向拉了一下門,不過想也知道籠子是鎖的。小向想起了她對付茶葉…噢不,是烏龍,時所用的破壞系咒語。
「霹麗卡霹麗拉拉,波波麗那貝貝魯多!」
小向的魔杖發出了強大的光芒,緊接著是一陣煙霧。不過煙霧消散後,牢籠仍沒被破壞。
「哎呀…原來你還會這種魔法啊…不過沒用的,這個牢籠封印了魔法,而且不受外界魔力影響。要不然我早就逃脫了。」
說得也是呢…
「說也好笑,這牢籠是我打造的。竟然被自己的打造的東西關住,我也真是沒用的。不過嘛…因為是我製造的,所以我還記得流程呢…甚至是開啟這牢籠的鑰匙我也記得…」
「真的嗎?可以告訴我詳細的過程嗎?」小向如此追問。
「可以是可以…不過為什麼要呢?」
「只要知道原料以及流程,就可以推算出最後的分子排列方法,我就可以造出一把鑰匙了。」
「這樣啊…好吧!我就告訴你吧!
鑰匙的原料是一個長條狀的物體,大致可分成$N$小塊。每塊的分子狀態可以由一個英文小寫字母表示。在鍛造的時候,每當我敲一次鑰匙,會有其中一段區間的分子狀態重新排列:可能是排成由小排到大的排列,也有可能是由大排到小,……」
接著希爾伯特把原料的狀態以及之後分子排列變化過程告訴了小向,而聰明的小向當然要用這些訊息推算出鑰匙的構造囉!
第一行有兩個正整數$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 |
輸出一個長度為$N$的字串,代表鑰匙最終的狀態。
abacdabcda → abacdadcba → abacacddba → cbaaacddba → cbcaaaddba → cbcaaaabdd
Problem Set / Description by Paupière
題目取自Codeforces.
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 24 |
2 | 5~9 | 36 |
3 | 10~14 | 40 |