Sqrt Algorithm

优雅的暴力啊！

The Begin

根号算法的优势在于好想好写，且支持维护更多的信息。

比如区间众数这种线段树维护不了的，而我们可以使用分块维护。

当然本篇文章所说的根号算法不只有分块，还有莫队，根号分治等一系列复杂度为 $\sqrt {n}$ 的算法。

本文肯定会有一个 Ynoi 的大分块的，只是时间问题。

Update on 2025.6.30：完结了，笔者真的写了 Ynoi 系列大分块中的一个。

整除分块

先从最简单的开始吧！

算法简介

形如让我们计算：$\sum_{i=1}^{n} \lfloor\frac{n}{i}\rfloor$ 这种式子，

我们发现，$\lfloor\frac{n}{i}\rfloor$ 在 $i$ 值不同时可能相同，而且是一段连续的区间。

所以我们考虑将这些地方一起计算。

具体地，枚举左端点 $l$，求出右端点 $r$，然后令左端点挪动到右端点 $r$ 上。

经过推导，我们得出了：

$$r=\lfloor \frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor$$

直接代入递推计算即可。

例题：模积和

推式子题，原题让求的是$$\sum_{i=1}^n \sum_{j=1}^m (n \bmod i)(m\bmod j),i≠j$$

长得太丑了，而且 $i≠j$ 丑到实在不忍直视。假定 $n\ge m$ ，得到如下：

$$\sum_{i=1}^n \sum_{j=1}^m (n \bmod i)(m\bmod j)-\sum_{i=1}^m (m \bmod i)(n\bmod i)$$

模数不好表达，考虑利用模数定义转化一下：

$$\sum_{i=1}^n \sum_{j=1}^m (n -i\times \lfloor\frac{n}{i}\rfloor)(m-j\times \lfloor\frac{m}{j}\rfloor) - \sum_{i=1}^m (m -i\times \lfloor\frac{m}{i}\rfloor)(m-i\times\lfloor\frac{n}{i}\rfloor)$$

然后发现减号前面那一项比较特别，写成这样：

$$\sum_{i=1}^{n}(n-i\times\lfloor\frac{n}{i}\rfloor) \times \sum_{j=1}^{m}(m-j\times\lfloor\frac{m}{j}\rfloor)$$

然后给它拆开，得到：

$$(n^2- \sum_{i=1}^{n}(i\times\lfloor\frac{n}{i}\rfloor))\times (m^2- \sum_{j=1}^{m}(j\times\lfloor\frac{m}{j}\rfloor))$$

然后前面这一车就可以拿整除分块算了，后面这一车做类似变化，最终得到一个

$$(n^2- \sum_{i=1}^{n}(i\times\lfloor\frac{n}{i}\rfloor))\times (m^2- \sum_{j=1}^{m}(j\times\lfloor\frac{m}{j}\rfloor))- \sum_{i=1}^{m}(m\times n- n\times i\times\lfloor\frac{m}{i}\rfloor-m\times i\times\lfloor\frac{n}{i}\rfloor+i^2\times\lfloor\frac{n}{i}\rfloor\times\lfloor\frac{m}{i}\rfloor)$$

这坨式子，发现后面的也是整除分块，接着就是整除分块快速求：

$$\sum_{i=1}^{n}i\times \lfloor\frac{n}{i}\rfloor$$

令 $l=i$，通过整除分块计算方式，我们知道 $r=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor} \rfloor$，所以 $r-l+1$ 就等于 $\frac{r\times(r+1)}{2}-\frac{(l-1)\times (l)}{2}$（$1->l,r$的前缀和相减），然后后面就是 $\frac{n}{l}$ ，然后就可以写完了。

后面的 $i^2$ 有平方和公式 $\frac{n\times (n+1) \times (2\times n+1)}{6}$ 。

代码

根号分治

算法简介

根号分治是一种平衡复杂度的思想。

比如有一道题，我们可以 $O(n^2)$ 预处理，$O(1)$ 回答或者不预处理，$O(n)$ 回答。

这两种复杂度我们都不能接受。

我们可以预处理 $\sqrt n$ 范围的，然后做到 $O(\sqrt n)$ 预处理，$O(\sqrt n)$ 回答。

上面是我之前学艺不精狗叫，根号分治不仅仅有上面的形式。（现在也学艺不精）

CF1806E Tree Master

我们将树分层，并对每层的节点数分讨：

如果当前层节点数大于 $\sqrt n$，这样的层数不超过 $ \sqrt n$ 个，我们直接进行搜索即可。
如果当前节点数小于 $ \sqrt n$，直接使用记忆化搜索即可。

总之，直接记搜即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10;
int n,m,a[N],fa[N],dep[N],sum[N],bel[N];
ll s[N];
ll f[N][500];
ll dfs(int x,int y){
    if(x==y) return s[x];
    if(sum[dep[x]]<480){
        if(f[x][bel[y]]) return f[x][bel[y]];
        return f[x][bel[y]]=dfs(fa[x],fa[y])+1ll*a[x]*a[y];
    }else return dfs(fa[x],fa[y])+1ll*a[x]*a[y];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){cin>>a[i];}
    for(int i=2;i<=n;i++){cin>>fa[i];}
    for(int i=1;i<=n;i++){
        s[i]=s[fa[i]]+1ll*a[i]*a[i];
        dep[i]=dep[fa[i]]+1;
        bel[i]=++sum[dep[i]];
    }
    for(int i=1,x,y;i<=m;i++){
        cin>>x>>y;
        cout << dfs(x,y) << '\n';
    }
    return 0;
}

P3645 雅加达的摩天楼

想一个最暴力的暴力，建 $ 9\times 10^8$ 条边，然后直接暴力最短路。

发现我们其实根本用不到每一条边，所以尝试不存储状态直接 bfs，然后拿 bitset 表示状态，发现过了？

为什么是对的呢？不应该队列里扔了一堆状态然后暴空间吗？

我们对跳跃能力分讨：

当 $p> \sqrt n$ 时，对于这只 doge，只有 $ \sqrt n$ 个位置。总计 $m \sqrt n$ 个状态。
当 $p<\sqrt n$ 时，对于每个点上状态，只有 $ \sqrt n$ 个不同的跳跃能力。总计 $n\sqrt n$ 个状态。

所以总状态数是非常正确的，并不会 MLE/TLE。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e4+10;
struct node{
    int id,p,step;
};
queue<node> que;
bitset<N> vis[N];
vector<int> vec[N];
bool v[N];
int n,m,s,t;
void push(int i,int p,int step){
    if(!v[i]){
        v[i]=1;
        for(int a:vec[i]){
            if(!vis[i].test(a)){
                vis[i].set(a);
                que.push({i,a,step+1});
            }
        }
    }
    if(!vis[i].test(p)){
        vis[i].set(p);
        que.push({i,p,step+1});
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int b,p;
        cin>>b>>p;
        if(i==0) s=b;
        if(i==1) t=b;
        vec[b].push_back(p);
    }
    if(s==t){cout << 0;return 0;}
    v[s]=1;
    for(int a:vec[s]){
        if(!vis[s].test(a)){
            vis[s].set(a);
            que.push({s,a,0});
        }
    }
    while(!que.empty()){
        auto to=que.front();que.pop();
        if(to.id-to.p==t || to.id+to.p==t){
            cout << to.step+1;
            return 0;
        }
        if(to.id+to.p<n){
            push(to.id+to.p,to.p,to.step);
        }
        if(to.id-to.p>=0){
            push(to.id-to.p,to.p,to.step);
        }
    }
    cout << -1;
    return 0;
}

CF710F String Set Queries

分治的标志：总量不超过……

对字符串长度进行根号分治：

长度小于 $ \sqrt n$ 的，上 Trie 树直接维护即可，询问直接暴力查询链和。
长度大于 $ \sqrt n$ 的，全扔去一边，然后用 KMP 维护，每次查询的时候重跑 KMP，然后暴力查询即可。

Trie 树上的操作都是 $ \sqrt n$ 的，总计是 $O(n \sqrt n)$。而大于 $ \sqrt n$ 的仅有 $ \sqrt n$ 个，所以总计也是 $O(n \sqrt n)$ 的。

所以总计的复杂度是 $O(n \sqrt n)$ 。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5+10;
int n;
struct Trie{
    struct node{
        int son[26];
        int cnt;
    }tr[N];
    int tot=0;
    void insert(char *s,int val){
        int u=0;
        for(int i=0;s[i];i++){
            char ch=s[i];
            int &son=tr[u].son[ch-'a'];
            if(!son) son=++tot;
            u=son;
        }
        tr[u].cnt+=val;
    }
    int query(char *s){
        int u=0,res=0;
        for(int i=0;s[i];i++){
            int c=s[i]-'a';
            if(!tr[u].son[c]) break;
            u=tr[u].son[c];
            res+=tr[u].cnt;
        }
        return res;
    }
}T;
struct KMP{
    int nxt[N];
    void build(const string &s,int len){
        memset(nxt,0,sizeof(nxt));
        int i=0,j=-1;nxt[0]=-1;
        while(i<len){
            if(j==-1 || s[i]==s[j]) nxt[++i]=++j;
            else j=nxt[j];
        }
    }
    int query(string s,char *qry){
        int res=0;
        int lens=s.size(),len=strlen(qry);
        build(s,s.size());
        for(int i=0,j=0;i<len;i++){
            while(j>0 && qry[i]!=s[j]) j=nxt[j];
            if(qry[i]==s[j]) j++;
            if(j==lens){
                res++;
                j=nxt[j];
            }
        }
        return res;
    }
}kmp;
string que[50];
char s[N];
int cnt,val[50];
int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
    scanf("%d",&n);
    for(int i=1,op;i<=n;i++){
        scanf("%d%s",&op,s);
        int len=strlen(s);
        if(op==1 || op==2){
            int v=(op==1 ? 1 : -1);
            if(len<=1000){
                T.insert(s,v);
            }else{
                que[cnt]=string(s);
                val[cnt++]=v;
            }
        }else{
            ll ans=0;
            for(int i=0;i<len;i++){
                ans+=T.query(s+i);
            }
            for(int i=0;i<cnt;i++){
                if(que[i].length()>len) continue;
                ans+=kmp.query(que[i],s)*val[i];
            }
            printf("%lld\n",ans);
            fflush(stdout);
        }
    }
    
    return 0;
}

分块

根号算法的代表，提起根号第一个想到的肯定是我们优雅的分块了！

算法简介

分块是重构和懒标记的结合，对于修改，通常使用“散块暴力，整块一起”的方法。

分块的作用主要是 平衡复杂度 和 维护线段树 等无法维护的信息。

将序列分块后，令块长为 $B$ ，可以得到单步复杂度为 $O(\frac{n}{B}+B)$。

根据均值不等式可以得到 $B=\sqrt n$ 时有最优复杂度 $O(\sqrt n)$。

接下来手把手教大家写分块模板题：

【模板】线段树 1

分块的预处理

分块预处理需要三个数组，$L_x , R_x , belong_i$ 分别表示，第 $x$ 块序列的左端点，右端点，原序列中的第 $i$ 个点属于哪一块。

分块区间加法

顺应上述的分块思想，对于整块的修改打上 tag ，对于散块就暴力修改。~~可能还用到了一点点的标记永久化的思想？~~

分块的区间查询

区间操作都很类似，只要注意一下计算时是否需要加上 tag 就行。

多种运算操作

根线段树一样，定义一个合理的优先级就行。

代码

序列分块

算法简介

最基本的分块，就是对原序列分成若干块。

教主的魔法

说人话：支持区间加法，查询区间内大于等于 k 的数的个数。

对于每一块都排好序，然后散块直接做就行了，对于整块，去二分查找后加上 $R_i-x+1$ 即可。

代码

由乃打扑克

第一道 Ynoi 题！

思路继承教主的魔法，整块内排序，考虑怎么求得第 k 小值。

去二分这个第 k 小值，然后查这个值是否是第 k 小就行啦。

代码

ycz的妹子

一句话题意：

单点修。
单点插入。
删除第 k 个值。
全局查询和。

线段树写起来显然很累，无论是脑子累或者是手累。

但是分块不一样，直接分块，单点修和单点插入显然，删除第 k 个值记录块内多少个有意义的值，然后直接跳块找即可。

甚至能支持区间查询和！

代码

值域分块

算法简介

如题，可以理解为权值分块

等这场战争结束之后

可撤销并查集+值域分块。

具体做法：离线建立版本树，离散化后值域分块维护每一块每个值出现次数，入树时进行修改或询问，出树时撤销修改。

然后就是 Ynoi 的经典卡常时刻，本题需要卡的是 20MB 的空间。

值域分块数组可以用 short。
块长设大一点。
使用版本树，别写在线！

代码

[Violet] 蒲公英

自然的想到离散化值域分块，因为求众数，要求多少个相同数，所以考虑前缀和。

具体而言，维护两个分块，一个 $s_{i,j}$ 表示第 $i$ 个块内的每个数的个数前缀和（对于 $i$ 统计），一个 $f_{i,j}$ 表示第 $i$ 块与第 $j$ 块之间的众数。这两个数组可以预处理。

对于询问，我们将询问分成三部分：

$———l——bl———————br——r————$

其中 $l,r$ 表示询问区间，$bl,br$ 表示若干个整块。可能的众数集合是：整块内的众数，$l\to bl$ 之间的某数，$br\to r$ 之间的某数。

散块暴力，整块一起，询问区间不能被分为两块时暴力，那么我们就做完了。

代码

[TJOI2007] 可爱的质数/【模板】BSGS

原式为：$a^l = b \pmod p$，化为 $a^{Am-n} = b \pmod p$，左右两侧同乘 $a^n$，式子变为：$a^{Am} = ba^n \pmod p$

我们可以预处理出所有的 $b\times a^n \bmod p$ 存入 hash 中，再去计算 $a^{Am} \bmod p$ 然后去查 hash 表中的数是否存在相同的数。

用 hash 的时间复杂度是 $O(\sqrt p)$ 。用 map 是 $O(\sqrt p \times \log p)$

代码

多少个1？

若干个 $1……1111 (N)$ 的形式，思考一下可以转化为 $\frac{10^n-1}{9}$ 的形式。

那么原题就变为求：

$$\frac{10^n-1}{9}=k\pmod m$$

略微化简，得到如下式子：

$$10^n = 9\times k +1 \pmod m$$

求最小整数 $n$ 满足上述式子，套BSGS板子。

中间需要开 __int128 ，或者使用快速乘。

原理是乘法分配律，可以试着推一把~~（反正我没推）~~。

代码

时间轴分块

算法简介

如题而言，对时间轴进行分块，逐个时间处理。

序列

带修也可以离线！

新增一个时间轴，两个修改中间的询问都是一个时间点。

我们先考虑只有一个数怎么做。

发现是查询前缀大于等于自己的数有多少个。

所以我们需要做一个查询排名和单点加法。

接下来考虑怎么做多个数。

我们离线后差分，将区间修改转为单点加法和前缀和即可。

代码

等我写俩题【TBD】

根号重构

算法简介

平衡修改和询问的复杂度的一个方式吧，具体而言设一个阈值 B，当操作积压到 B 的时候再去处理。

桥梁

观察题目可以发现，我们能想出两种暴力做法：

暴力模拟所有操作，询问时搜索，是 $O(n^2)$ 的。
离线询问按降序排序，每次回答时重跑时间轴之前的操作，然后拿可撤销并查集维护连通性，也是 $O(n^2\log n)$ 的。

发现这两种暴力从截然不同的角度出发，一个枚举边，一个枚举操作，所以我们使用分块将这两个均摊一下。

简单而言，定义一个阈值 $B$，当积压的操作达到 $B$ 的时候处理当前所有操作，同样使用可持久化并查集维护一下。

复杂度很好玩了，我们会把操作分成 $\frac{q}{B}$ 块，每块最多 $B$ 个

将 B 带入上面两个暴力的复杂度，得到最后式子是 $O(qB\log n + \frac{qm\log m}{B})$ ，$B$ 取个 $\sqrt {mlogn}$ 据说跑的飞快，但是我 $B$ 取了个附近的定值，也跑过了。

代码

莫队

算法简介

莫队是优雅的暴力，通过挪动左右指针来移动到下一个询问区间。

离线算法，不带修复杂度为 $O(n\sqrt n)$，带修能做到 $O(n^{\frac{5}{3}})$。

需要将询问排序：如果左端点在同一块内，右端点升序，否则左端点升序。

可以玄学优化，左端点在偶数块右端点升序，否则降序。

小Z的袜子

莫队模板题，排完序直接做就行了。

代码

[国家集训队] 数颜色 / 维护队列

带修莫队模板题。

在莫队基础上加一维时间轴，先按时间轴排序，如果是同一时间轴的则按上述莫队正常排序。

考虑时间变动的影响，然后去更新消除影响即可。

复杂度经证明取 $B=n^{\frac{2}{3}}$ 最优，所以总体复杂度是 $O(n^{\frac{5}{3}})$

代码

其他例题

穿插上述各种题目，可能莫队偏多，因为纯考分块的只有lxl大分块。

Rmq Problem / mex

显然值域分块再加上前缀和就可以解决出现最小自然数的问题，配合莫队实现区间蠕动即可。

代码

如果你调半天调不出来，可以看看 while() 是不是写成了 if() 。~~这玩意我看了半小时~~

作业

会了上面那个，这个也就很显然了。

值域分块套上莫队，维护两个数组一个是所有和，一个是不同位置的和，写两个询问就好。

代码

异或序列

发现关键性质：给异或做前缀和，一段区间的异或值等于 $arr_r $ ^ $arr_{l-1}$ 然后莫队的移动我们就可以 $O(1)$ 了。

代码

区间(range)

不能做除法，O(1) 求数列中定长为 k 的所有区间的数的积模 P（P不保证为质数，不保证有逆元）。

首先会想到前缀积和后缀积，发现正常的前缀后缀积不能拼出来一个长度为 k 的区间。

考虑以 k 为块长分块，每块内做前缀后缀积，然后所有定长为 k 的恰好被分成两段（或者一整段）。

然后就可以直接写了。

代码

小B的询问

莫队的基础题，先把莫队扔上去。

考虑莫队维护区间平方和，难道我们要像线段树一样维护一个区间和，再维护一个区间平方和吗？

我都写莫队了，先把贡献删了，修改后再加回去就行。

代码

The End 去往那五彩斑斓的世界

故事终于来到最后，你打败了路上的所有小怪，精英怪，你来到了最终 boss 之前。

你攥紧了手中的宝具：[突刺贯穿的第二分块]。

仰望着漆黑的天空，轻抚着狂乱的风暴：

按照故事的剧本，打败最终 boss 之后，你就到了五彩斑斓的世界。

是的，是时候动身了，还有人在等着我们。

fun fact：主播为了找一道能做的大分块找了一个多小时，最终还是回到了这道题

给定长度为 $n$ 的序列，$m$ 次操作

把区间 $[l,r]$ 中大于 $x$ 的数减去 $x$。
查询区间 $[l,r]$ 中 $x$ 的出现次数。

$n\le 10^6 , m\le 5\times 10^5 ,0\le a_i,x \le 10^5+1$

拿到手第一刻很懵，相同的数可以并查集缩一起，查询时累加并查集大小就行。

但是我们似乎避不开要枚举值域，那我们就需要分析值域上的性质了。

假定我们现在序列中最大的数是 mx，减去的数是 x，n 为个数，m 为操作数，v 为值域。

分两种情况讨论：

$2x\ge mx$, 那么全局最大值变为：$mx=mx-x$
$2x < mx$, 我们可以先令 $\le x$ 的数 +x ，那么全局就都比 x 大了，此时给全局打一个减法 tag，全局最大值依然变为：$mx=mx-x$ 。

发现全局最大值单调不增！

那么我们最大值上界是 $10^5$ 的，而操作却有 $5\times 10^5$ 次。

这是一个很好的均摊，我们直接枚举修改了哪些值即可。总计是 $O(v)$ 左右的。

那么复杂度有了保证，再想想实现的细节。

对于整块：
修改时直接遍历需要改的值，然后并查集合并。
询问时也是直接回答就行。
修改 $O(\sqrt n)$ ，询问 $O(1)$ 的。

对于散块：
修改时将所有值复原，再修改。
询问时也将所有值复原，再遍历。
都是 $O(\sqrt n)$ 的。

注意值域有 0，这玩意放进并查集里完蛋了，但是 0 不会变成负数，也不会有任何数变成 0。
所以可以直接预处理所有 0 的情况，做前缀和即可。

当然做完上述事情就已经可以 AC 另一道题了：CF896E
fun fact：本题和 lxl 提出的珂朵莉树是一场比赛的题。

本题 lxl 卡了线性空间，主播跟 lxl 斗智斗勇一中午终于调过。
fun fact：主播写的空间常数略大的线性空间也被卡飞了。

发现块与块之间相互独立，将询问离线下来，去每一个块里跑一遍，然后累加答案就行。

最终复杂度是：$O(m\sqrt n + n\sqrt v)$ 左右吧，不太会算。

代码

来，出发吧，去选择那独一无二的明天

除非 lxl 来讲课，不然这是主播最后一道 Ynoi 大分块系列题。

LOADING

The Begin

整除分块

算法简介

根号分治

算法简介

分块

算法简介

序列分块

算法简介

值域分块

算法简介

时间轴分块

算法简介

根号重构

算法简介

莫队

算法简介

其他例题

The End 去往那五彩斑斓的世界