题意理解及思路转换详见: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\) 是一个桶代表该区间内该颜色位置是否形成一个等差数列。
不过莫队写起来码量比树状数组大,速度还慢约 \(2s\) ,所以如果想得到树状数组还是不建议写莫队的。