分块算法 Maigc-Block-Algorithm

ajcxsu
ajcxsu 2018年04月14日
  • 50 次阅读

分块的易错的常用操作。

联动:https://acxblog.site/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://acxblog.site/archives/TLEBA.html
本文采用 CC BY-NC-SA 3.0 协议进行许可