• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CF351D Jeff and Removing Periods Ⅱ

开发技术 开发技术 6小时前 1次浏览

题意理解及思路转换详见: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) ,所以如果想得到树状数组还是不建议写莫队的。


程序员灯塔
转载请注明原文链接:CF351D Jeff and Removing Periods Ⅱ
喜欢 (0)