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

————————

See link for the understanding of the topic and the transformation of ideas

Similarly, we only need to preprocess the \ (NXT \) array and \ (del \) array, and then directly maintain them.

Let’s put the most critical function:

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;
    }
}

Here \ (L \) is the left end point of the maintained interval, \ (ZX \) (random variable name) refers to whether the change point is at the head or tail of the queue, \ (DQ \) is a double ended queue for maintaining the value of \ (del \) in the current interval, \ (NB \) is a bucket, which represents whether the color position in the interval forms an equal difference sequence.

Code

However, the code size of Mo team is larger than that of tree array, and the speed is about \ (2S \), so it is not recommended to write Mo team if you want to get tree array.