2020.05.16【省選B組】模拟

T1：直接二分答案，然後用哈希判斷答案是否合法。

比賽時直接枚舉了答案，于是就逾時了。

T2：很容易想到求出每一種顔色的最左和最右的位置，那麼這一種顔色就是要覆寫從最左到最右這一個區間。在所有區間中不能有相交又不包含的，剩下的可以通過拓撲來求最優解。

實作的時候可以先不管所有區間合不合法，先按照合法的情況做一遍，做的過程中模拟染色，最後判斷一下染出的結果是否與給出的一緻。建拓撲圖和染色的過程可以用線段樹來維護。

T3：這題比較巧妙。

首先我們從小到大枚舉序列中的數，然後求出以目前這個數為三元組中的最小值的貢獻。具體做法就是用并查集把比x小的數并在一起，在求x的貢獻時就用并查集找到左邊3個比x大的數和右邊3個比想大的數。畫一下圖分類讨論一下就可以求出不同情況的貢獻。在每次求完x的貢獻之後維護一下并查集就可以了。