#38544: 解題報告


dfd8282@gmail.com (fishhh)


我的複雜度 O(nlogn)

應該可以用單調對列優化我的作法變成 O(n)   吧

 

 

枚舉起點,二分搜從起點開始第一個小於P的位置(在 sparse table 上二分搜),再開一個vector紀錄每一個顏色出現過哪些位置。

再透過一次二分搜計算比第一個小於P的位置的後面有幾個跟起點顏色相同的數量即可(這一步應該也可以壓成O(1))