C/C++教程

CF351D Jeff and Removing Periods Ⅱ

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

这篇关于CF351D Jeff and Removing Periods Ⅱ的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!