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\) ,所以如果想得到树状数组还是不建议写莫队的。

上一篇:点分治 学习笔记


下一篇:A Dangerous Maze (概率期望)