CF351D Jeff and Removing Periods Ⅱ

題意了解及思路轉換詳見：​​link​​

同樣的道理，我們隻需要預處理出來 \(nxt\) 數組和 \(del\) 數組，然後直接莫隊維護就可以了。

擺一段最關鍵的函數吧：

void work(int l , int zx){
if(dq[a[zx]].empty()) {
nb[a[zx]] = false;
maxi --;
return ;
    }
int now = dq[a[zx]].back();
if(l <= now){
if(nb[a[zx]] == true) maxi --;
nb[a[zx]] = false;
    }
if(l > now){
if(nb[a[zx]] == false) maxi ++;
nb[a[zx]] = true;
    }
}
      

這裡的 \(l\) 是維護的區間的左端點，\(zx\)（随便起的變量名）指的是變化的點是在隊頭還是在隊尾，\(dq\) 是維護目前區間 \(del\) 數值的雙端隊列，\(nb\) 是一個桶代表該區間内該顔色位置是否形成一個等差數列。

​​Code​​

不過莫隊寫起來碼量比樹狀數組大，速度還慢約 \(2s\) ，是以如果想得到樹狀數組還是不建議寫莫隊的。