分块的易错的常用操作。

联动：https://pst.iorinn.moe/archives/TLEBA-B.html

To 各位想要学习分块的同学

请移步：http://hzwer.com/8053.html
把这 9 题刷完就差不多了（逃

下面都是扯淡，但可以教你分块下标怎么标（

分块下标法 1

假设块的大小为 m。则令 $i$ 的块下标为 $\left \lceil \frac{i}{m} \right \rceil$。
转换成代码就是pos[i]=(i-1)/m+1，即ceil(pos[i])。

那么第 $i$ 块的左右下标为 $l=m(i-1)+1,\ r=mi$。

分块下标法 2

不太在意每个块的左右下标的话，直接令 $i$ 的块的下标为 $\left \lfloor \frac{i}{m} \right \rfloor+1$。主要用于判断相邻两个数的块是否相等。常见于莫队。

带插入的分块

在某分块大小 $\geq 2\sqrt{n}$ 时（或每进行 $\sqrt{n}$ 次操作），选择对块进行暴力重构，最坏复杂度为 $O(2n\sqrt{n})$。
使用 vector 会爽一些。

分块的大小

在下并不会均值不等式（逃

降智打击

WA

    for(int i=l;i<=br[pos[l]];i++)
        inc(v[i],c);
    if(pos[l]!=pos[r]) {
        updblock(pos[r]);
        for(int i=r;i>=bl[pos[r]];i--)
            inc(v[i],c);
    }
    for(int i=pos[l]+1;i<=pos[r]-1;i++)
        inc(tag[i],c);

AC

    for(int i=l;i<=br[pos[l]] && i<=r;i++) // Surprise mother fxxker
        inc(v[i],c);
    if(pos[l]!=pos[r]) {
        updblock(pos[r]);
        for(int i=r;i>=bl[pos[r]] && i>=l;i--) // Surprise mother fxxker
            inc(v[i],c);
    }
    for(int i=pos[l]+1;i<=pos[r]-1;i++)
        inc(tag[i],c);

降智打击 x2

TLE

if(pos[l]!=pos[r]) {
        for(_rg int i=r;i>=bl[pos[l]];i--) {
            nt=cnt(l,r,v[i]);
            if((nt==times && v[i]<ret) || nt>times) times=nt, ret=v[i];
        }
    }

AC

if(pos[l]!=pos[r]) {
        for(_rg int i=r;i>=bl[pos[r]];i--) { // Surprise mother fxxker
            nt=cnt(l,r,v[i]);
            if((nt==times && v[i]<ret) || nt>times) times=nt, ret=v[i];
        }
    }

其实还应该加上i>=l....

本文链接：https://pst.iorinn.moe/archives/TLEBA.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆