【TIOJ 1169】氣球博覽會

原題連結：http://tioj.infor.org/problems/1169

首先要先想到第三子題怎麼做
對於每一個顏色，都開一棵線段樹
對於一個顏色K的線段樹維護：
1.從左邊開始不含K的最長區間
2.從右邊開始不含K的最長區間
3.這個區間不含K的最長區間
維護並不難想也不難寫，總複雜度O(2^cN+QlgN)，空間複雜度O(2^CN)

問題在當C到24時，不管是時間還是空間都有問題
我們首先觀察到，在尚未有任何氣球的時候，對於每個顏色的線段樹長相都一樣
先把原序列當成N個的單點修改操作，這樣每個修改操作一定只會到動到lgN個線段樹的節點
那這裡就可以用動態開點的方式，如果記憶體是空的表示這個區間絕對沒有該顏色，可以直接把答案填滿，這樣也不用預處理2^cN。
至於詢問操作就照原本的寫，只要注意不要讀到空的記憶體就好了
複雜度O((N+Q)lgN)，空間上如果對顏色離散化或用map會更好，不過我是直接硬開2^24個指標就是了XD