分块 and 莫队

王昊岩123 · 2024-04-26 21:58:30 · 算法·理论

1.分块

简而言之，就是把数据分成若干块，每块都有一些信息（如区间和等），对于区间操作，包含整个块的部分用存储的信息。“边角料”部分使用暴力

例题：线段树1

直接上码子理解原理

int n,m,len;//len是块长，与复杂度有关
int a[N],num[N],sum[N],tag[N];
//分别是原始数据，每个数据所属块的编号，块i的元素和，块i的操作记录（≈lazytag）
void add(int l,int r,int x)
{
    int numl = num[l];
    int numr = num[r];//获得左右端点所在块
    if(numl == numr)//在块内（不一定包含块）
    {
        for(int i = l;i <= r;i++) a[i] += x,sum[numl] += x;//暴力法
        return;
    }
  //若不在块内，那么被完整包含的是块numl + 1 ~ numr - 1，numl,numr就是边角料
    for(int i = l;num[i] == numl;i++) a[i] += x,sum[numl] += x;//左边的边角料，要保证不出块
    for(int i = numl + 1;i < numr;i++) tag[i] += x,sum[i] += len * x;//被包含的区间，直接用块的信息处理
    for(int i = r;num[i] == num[r];i--) a[i] += x,sum[numr] += x;//右边的边角料
}
ll query(int l,int r)//原理同上
{
    ll ans = 0;
    int numl = num[l],numr = num[r];
    if(numl == numr)
    {
        for(int i = l;i <= r;i++) ans += a[i] + tag[numl];
        return ans;
    }
    for(int i = l;num[i] == numl;i++) ans += a[i] + tag[numl];
    for(int i = numl + 1;i < numr;i++) ans +=  sum[i];
    for(int i = r;num[i] == numr;i--) ans += a[i] + tag[numr];
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    len = sqrt(n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&a[i]);
        num[i] = (i - 1) / len + 1;//处理每个元素所属块
        sum[num[i]] += a[i];//块的元素和
    }   
    for(int i = 1;i <= m;i++)
    {
        int op;
        int l,r,x;
        scanf("%d",&op);
        if(op == 1)
        {
            scanf("%d%d%d",&l,&r,&x);
            add(l,r,x);
        }
        else
        {
            scanf("%d%d",&l,&r);
            printf("%lld\n",query(l,r));
        }
    }
    return 0;
}

显然，这种东西爆难度肯定是在处理思想上整大活

P2801 教主的魔法

click

区间加法维护不说，考虑比大小

如何确认一整个块的元素都\geqslant c？

只需要块内最小值\geqslant c即可

如果满足，那么贡献就是len（块长）

那不满足呢？

way 1：记录下块的左右端点，暴力查找

for(int i = numl + 1;i < numr;i++) 
{
    if(minn[i] >= c) ans += len;
    else
    {
        for(int j = le[i];j <= ri[i];j++)
            if(a[j] + tag[i] >= c) ans++;//块内硬找
    }
}

可水得90pts，相当的不错

那么就要考虑如何优化

我们可以新建一个数组，存的是元素单调的块，这样就可以二分找点，更快

注意，该数组必须时刻与原始数组同步，即对于那些直接修改元素而非tag的边角料部分，要把整个块重新拷一遍再排序

void add(int l,int r,int k)
{
    //对于所有a[i] += k的操作，都要把块重新赋一遍再排序
    //排序[l,r]是sort(b + l,b + r + 1);
    int numl = num[l],numr = num[r];
    if(numl == numr)
    {
        for(int i = l;i <= r;i++) a[i] += k;
        for(int i = le[numl];i <= ri[numl];i++) b[i] = a[i];
        sort(b + le[numl],b + ri[numl] + 1);
        return;
    }
    for(int i = l;num[i] == numl;i++) a[i] += k;
    for(int i = le[numl];i <= ri[numl];i++) b[i] = a[i];
    sort(b + le[numl],b + ri[numl] + 1);
    for(int i = numl + 1;i < numr;i++) tag[i] += k;
    for(int i = r;num[i] == num[r];i--) a[i] += k;
    for(int i = le[numr];i <= ri[numr];i++) b[i] = a[i];
    sort(b + le[numr],b + ri[numr] + 1);
}
int check(int l,int r,int id,int c)
{
    int l1 = l,r1 = r;
    int res = 0;
    while(l1 <= r1)
    {
        int mid = l1 + r1 >> 1;
        if(b[mid] + tag[id] >= c) res = mid,r1 = mid - 1;
        else l1 = mid + 1;
    }
    if(res == 0) return 0;//这里是个坑：如果找不到点,res = 0，要特判
    return r - res + 1;
}
int query(int l,int r,int c)
{
    int ans = 0;
    int numl = num[l],numr = num[r];
    if(numl == numr)
    {
        for(int i = l;i <= r;i++) if(a[i] + tag[numl] >= c) ans++;
        return ans;
    }
    for(int i = l;num[i] == numl;i++) if(a[i] + tag[numl] >= c) ans++;
    for(int i = numl + 1;i < numr;i++) 
    {
        if(minn[i] + tag[i] >= c) ans += len;
        else ans += check(le[i],ri[i],i,c);
    }
    for(int i = r;num[i] == numr;i--) if(a[i] + tag[numr] >= c) ans++;
    return ans;
}

P3203 [HNOI2010] 弹飞绵羊

click

按题意暴力40pts

采用分块：块内的跳跃合并掉，因此定义以下几个量：

那么查询时可以用这几个量优化

类似上题：单点修改涉及的块都要更新一遍

void cal(int x)
{
    int u = x;
    int numx = num[x];
    int cnt = 0;
    while(num[x] == numx && x < n) x += a[x],cnt++;
    if(x < n) nxt[u] = num[x];
    else nxt[u] = -1;//把[n,+无穷]这个块定位-1号块
    sum[u] = cnt; 
    fi[u] = x;
}
void init(int l,int r) {for(int i = l;i <= r;i++) cal(i);}
int query(int pos)
{
    int id = num[pos];
    int ans = 0;
    while(id != -1)//未弹飞
    {
        id = nxt[pos];//下一步块的编号
        ans += sum[pos];
        pos = fi[pos];//更新落脚点
    }
    return ans;
}
void add(int pos,int k)
{
    int newnum = num[pos];
    a[pos] = k;
    init(le[newnum],ri[newnum]);//更新涉及的块
}

这样60pts

再优化就是更新sum,fi,nxt的方法，对于这种链式转移，可以想到继承法：如果当前点的下一步更新过了，就用更新好的信息更新该点

写了半天反而变20，后来才发现倒序来就好写了

//后来发现nxt没什么用
void add(int pos,int k)
{
    a[pos] = k;
    for(int i = ri[num[pos]];i >= le[num[pos]];i--)
    {
        if(i + a[i] > ri[num[i]])
        {
            fi[i] = i + a[i];
            sum[i] = 1;
        }
        else
        {
            fi[i] = fi[i + a[i]];//由于是倒序，所以i + a[i]就是更新好的点，直接用
            sum[i] = sum[i + a[i]] + 1;
        }
    }
}

P4168 [Violet] 蒲公英

click

正解是求区间众数

要快速求出某种颜色在区间[l,r]的出现次数，可以将该颜色出现的位置都记录下来，记该数组为pos，然后二分找到pos中第一个大于等于l和r的元素，二者在pos中对应下标的差值就是该颜色在区间中的出现次数

对于[l,r]中的众数，要么在整块内，要么在边角料内，所以只需遍历边角料部分的颜色，来看看有没有众数

还可以预处理出连续若干整块的众数，这样对于从numl + 1到numr - 1的整块的众数查询更快

考虑到查询次数中有区间二分操作，所以块长最优并非\sqrt n，经过实验得到

上图为gxyzoj结果,洛谷比这松的多，以至于可以放肆使用STL

代码

颜色

click

与上题类似

处理区间前缀和，定义sum_{i,j,k}表示第i歌块到第j个块中1 \sim k颜色的个数平方和

这里就出现了一个问题：a^2 + b^2 \neq (a+b)^2，也就是说，举个例子，颜色1在整块中出现了k次，sum里存的就是k^2，如果边角料里又出现了l次颜色1，那么答案应当是(k+l)^2，不能由k^2 + l^2得到

此时就有一个神奇小技巧：比如k = 4,l = 6，那么答案应为100

而100 = 4 ^ 2 + \sum\limits_{i = 0}^{6 - 1}[2(4+i)+1]

也不难证明：

所以另定义一个num_{i,j,k}表示块i到块j中颜色k的数量，在统计边角料的时候就用运用上面的计算方法来算

有正确性的码子

接下来就是卡时大赛

然而运用数学工具计算得到

（x是块长）

不行啊 （这还没细算其他小常数，后来发现题解也过不去白卡了一下午）

2.莫队

对分块的优化，通过排序查询区间，从第一个区间不断扩展到其他询问区间得到答案，优化了时间，但也带来了局限性，比如修改受限制，必须离线等

排序时结合分块，以左端点所在的块的编号为第一关键字，以右端点为第二关键字

一般用来解决区间内不同元素个数的问题

询问数和元素数近似相同时复杂度为O(n\sqrt n)

变式有带修/树上/回滚莫队等

引子：HH的项链

是用过不去的莫队解决的经典例子，至少原理基础

bool cmp(node x,node y)
{
    if(num[x.l] != num[y.l]) return num[x.l] < num[y.l];
    else return x.r < y.r;
}//排序
void add(int x)
{
    if(!cnt[x]) res++;//如果该颜色先前未出现，则种类加一
    cnt[x]++;   
}
void del(int x)
{
    cnt[x]--;
    if(!cnt[x]) res--;//如果扔掉该点后颜色没了，种类数减一
}
//这里add和del顺序不同是因为add是探索未知，先勘测再更新，del是去除旧本，先去掉再看影响
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
    scanf("%d",&m);
    len = max(1,(int)sqrt((double)n * n / m));
    for(int i = 1;i <= n;i++) num[i] = (i - 1) / len + 1;
    for(int i = 1;i <= m;i++)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id = i;
    }
    sort(q + 1,q + m + 1,cmp);
    for(int i = q[1].l;i <=q[1].r;i++)
    {
        if(!cnt[a[i]]) res++;
        cnt[a[i]]++;
        ans[q[1].id] = res;
    }
    for(int k = 2,i = q[1].r,j = q[1].l;k <= m;k++)
    {
        while(i < q[k].r) add(a[++i]);//范围是i+1~r
        while(i > q[k].r) del(a[i--]);//范围是r+1 ~ i
        //上面两个while只会执行一个，下面同理
        while(j < q[k].l) del(a[j++]);
        while(j > q[k].l) add(a[--j]);
        ans[q[k].id] = res;
    }
    for(int i = 1;i <= m;i++) printf("%d\n",ans[i]);
    return 0;
}

code

P4396 [AHOI2013] 作业

难点在于值域在不断变化，考虑到莫队的操作不遍历区间内部，所以值域变化时答案的维护变得困难

那我们不妨考虑对值域开刀

我们不妨把值域看做下标，那么个数就是在求一个区间为[a,b]的权值（个数）数组的区间和，种类数相当于求一个布尔数组的区间和，l,r是区间修改

也就是说，我们可以使用莫队跳l,r来完成区间修改，再用一个方法完成区间查询，共同实现类似线段树的操作

方法可以用分块，好写

code

[WC2013] 糖果公园

click

树上莫队 + 带修莫队

但是还可以通过dfs得到线性序列来搞普通带修

如果使用普通的dfs序列的话，考虑到in_x \sim out_x是x的子树内所有点，用区间一概而论会算上一些非路径上的点，那么就要换成欧拉序，优点就是非路径上的点会出现两次（回溯的时候会再记一次，但走一条路径肯定不用回溯），可以通过奇偶性筛掉

void dfs(int x,int fa)
{
    in[x] = ++ tot;
    id[tot] = x;
    dep[x] = dep[fa] + 1;
    f[x][0] = fa;
    for(int i = 1;i <= 20;i++) f[x][i] = f[f[x][i - 1]][i - 1];
    for(int i = head[x];i;i = e[i].next)
    {
        int k = e[i].to;
        if(k != fa) dfs(k,x);
    }
    out[x] =++ tot;//写++是欧拉序，不写就是普通dfs序
    id[tot] = x;
}

接下来就是如何设定区间，需要分类讨论

• u,v$中间不“拐弯”，特点是$lca(u,v) = u/v$，此时区间就是$[in_u,in_v]
• u,v$中间要拐弯，此时路径就相当于从$u/v$的子树出来再走到另一子树的根，所以是$[out,in]$，角标根据$u,v$对应的$in,out$大小而定，但角标肯定是一个为$x$，一个为$y

最后一点：考虑到lca可能会被回溯但却在路径上，所以要特殊处理

具体实现

P2325 [SCOI2005] 王室联邦

click

这题就要直接在树上分块

直接在树上分块的要点：

• 属于同一块的节点间的距离不超过给定块的大小

• 每个节点都要属于一个块

• 编号相邻块的距离不能太大

• 块大小要相对均匀

具体实现的话，我们可以dfs的同时搞一个栈，搜到一个元素就让他入栈，一旦栈的大小大于设定的块的大小，就把栈内的元素划为一个块，dfs完栈内剩下的点作为一个块

但好像只有分块没莫队啥事

那么如何设定块的大小呢？

我们可以从剩下的数量考虑，事实上，上面方法的最后一步不一定成立，因为此时剩下的可能不足B个，此时最暴力的思想就是把剩的点并入最后一个块，假设块的大小是x，栈内最多剩下x-1个，那么2x-1 \leqslant 3B，得到x \leqslant 1.5B + 0.5，考虑到不止一种解法，为了方便，大小设成B就行

接下来搞省会

样例就告诉了我们省会放块里风险巨大，因为可能从某点要先过它和省会的lca再到省会，我们难以把控lca的位置，所以不妨就把省会设为块内所有点的lca，换句话说就是所有点所在的子树的根

那么综合一下就可以得到分块方法：

void dfs(int x,int fa)
{
    int siz = tot;
    for(int i = head[x];i;i = e[i].next)
    {
        int k = e[i].to;
        if(k != fa)
        {
            dfs(k,x);
            if(tot - siz >= B)
            {
                sum++;
                hui[sum] = x;
                while(tot != siz) sheng[stk[tot--]] = sum;//把x子树内的点划成一个快
            }
        }
    }
    stk[++tot] = x;
}
...
if(tot != 0)
{
    if(tot >= B)
    {
        hui[++sum] = 1;
        while(tot) sheng[stk[tot--]] = 1;
    }
    else
    {
        while(tot) sheng[stk[tot--]] = sum;
    }
}

结合错误提示发现应当是建了不合法的省或是省会没选好，这时再想一下就会发现，剩的点应该是聚在某个很靠下子树的一坨，此时贸然设置1为省会可能会导致路径横穿其他省的城市导致错误，所以不妨直接并入，因为事实上考虑到dfs时的方法，结束后其实也最多剩下B个（B-1个子树内部点和一个无处安放的子树根），那么并入的大小也顶多是2B-1 + B = 3B - 1，刚刚好

坑点：可能最初城市就不足B个，此时dfs啥也没干，暴力一下就行了

record

ps：明显看到树上分块方式和题目性质有很大关联

ps2:又翻了翻相关的树上莫队题目，发现大部分方法还是压成欧拉序来搞，这种树上直接分块的应用较少，至于原因，可能是因为维护麻烦的缘故

更多题目：

• COT2和bzoj3757苹果树是基础操作
• 有点难的Haruna's Breakfast和做这道题前要做的前置芝士

歴史の研究

click

回滚莫队

看完原理感觉更傻X了

大概意思就是放弃删除操作（题目中修改操作不利于维护答案），抛弃/加上一整段数字来为下一个询问做准备，保证只通过扩区间的方式就可以获得询问答案

又考虑到左端点在同一块内时可以使得右端点单调，但左端点无法保证，所以每次调整（扔掉）的都是左边

经过观察可以发现：每次初始的左端点（i'）就是左端点所在块的右端点+1（因为左端点可能恰好在块右端上，初始化成右端点的话右端点将不会计入答案）

又考虑到左端点跨块时右端点单调性未知，所以先前的个数等数据全部扔掉

具体实现

然后T了几个

后来发现把cnt开成和N一样是10^5就行了。。。原来开的10^6

code（含注释）

permu

click

回滚，不想做了