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
\]
直接代入递推计算即可。
模板题：UVA11526 H(n)
套公式直接做即可。
代码
例题：模积和
推式子题，原题让求的是$$\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
#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
#define ll long long
using namespace std;
const int N = 3e4+10;
struct node{
int id,p,step;
};
queue
bitset
vector
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 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 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 #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 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 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 ans+=T.query(s+i); } for(int i=0;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\) 取了个附近的定值，也跑过了。 代码 根号重构 算法简介 你说得对，但是 单点修+维护抽象信息 为什么不想根号重构被修改的块。 难道你想写什么 奇技淫巧线段树 或者 大力 LCT 吗？ 又或者什么 神奇转化+扫描线 吗？ 楼房重建 题意：单点修+固定起点查上升子序列长度。 正解是单侧递归线段树或分块重构。 这种看起来很抽象的信息为什么不拿分块！ 对于每一块，用 vector 存上升子序列，查询时二分查找即可。 对于修改，将所在块的 vector 清空后直接重构。 两个操作复杂度均为 \(O(\sqrt n)\)，显然可以轻松通过本题。 #include using namespace std; const int N=1e5+10; int n,m,a[N],len,bel[N],s=2e9; vector void init(){ for(int i=1;i<=n;i++){ bel[i]=(i-1)/len+1; } } void modify(int x,int k){ a[x]=k; double mx=0; vec[bel[x]].clear(); for(int i=(bel[x]-1)*len+1;bel[i]==bel[x] && i<=n;i++){ if(!a[i]) continue; double tmp=(double)a[i]/(1.0*i); if(tmp>mx) vec[bel[x]].push_back(tmp),mx=tmp; } } int find(int x,double val){ return vec[x].end()-upper_bound(vec[x].begin(),vec[x].end(),val); } int query(){ int res=0; double mx=(double)a[s]/(1.0*s); for(int i=1;i<=bel[n];i++){ res+=find(i,mx); if(vec[i].empty()) continue; double tmp=(*(--vec[i].end())); if(mx } return res+1; } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m; len=sqrt(n*log(n)); init(); for(int i=1;i<=m;i++){ int x,k; cin>>x>>k; s=min(s,x); modify(x,k); cout << query() << '\n'; } return 0; } 弹飞绵羊 这次你没法选了，不写 分块 你难道写 LCT 吗？ 下文称 \(i\) 到达的位置为 \(to_i\) 有个非常自然的暴力： 询问时直接依次遍历模拟，然后得出答案。询问：\(O(n)\) 修改：\(O(1)\)。 当然稍加思索，如果没有修改，答案就是一段 \(to_i\) 的前缀和，可以预处理。询问：\(O(1)\) 修改 \(O(n)\)。 两个暴力都有了，符合分块平衡复杂度的必要条件了，那就分块呗。 把指向与 \(i\) 一个块内的 \(to_i\) 并列起来，然后做前缀和，查询时直接查询前缀和后跳到下一块。 可能上面说的有点抽象，可以看看代码。（这题还有助于加强对前缀和的理解欸） 复杂度分析： 我们把每块内的 \(to_i\) 并到一起，指向 \(to_{R_i}\)，所以查询最多遍历 \(\sqrt n\) 个块。 修改直接重构一整块就行，最多 \(\sqrt n\) 个数。 所以复杂度是 \(O(n\sqrt n)\) 的。你 LCT 跑得过吗？！（跑过了我就去调块长） #include #define ll long long #define B 500 using namespace std; const int N = 2e5+10; int n,m,a[N]; int to[N],bel[N],L[N],R[N],tot,cnt[N]; void init(){ tot=(n-1)/B+1; for(int i=1;i<=n;i++){ bel[i]=(i-1)/B+1; } for(int i=1;i<=tot;i++){ L[i]=(i-1)*B+1; R[i]=min(i*B,n); } for(int i=1;i<=tot;i++){ for(int j=R[i];j>=L[i];j--){ if(j+a[j]<=R[i]){ cnt[j]+=cnt[j+a[j]]+1; to[j]=to[j+a[j]]; }else{ cnt[j]=1; to[j]=j+a[j]; } } } } void modify(int x,int k){ a[x]=k; for(int i=R[bel[x]];i>=L[bel[x]];i--) cnt[i]=to[i]=0; for(int i=R[bel[x]];i>=L[bel[x]];i--){ if(i+a[i]<=R[bel[x]]){ cnt[i]+=cnt[i+a[i]]+1; to[i]=to[i+a[i]]; }else{ cnt[i]=1; to[i]=i+a[i]; } } } int query(int x){ int res=0; while(x<=n){ res+=cnt[x]; x=to[x]; } return res; } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } init(); cin>>m; for(int i=1;i<=m;i++){ int op;cin>>op; if(op==1){ int x;cin>>x;x++; cout << query(x) << '\n'; }else{ int x,y;cin>>x>>y;x++; modify(x,y); } } return 0; } 莫队 算法简介 莫队是优雅的暴力，通过挪动左右指针来移动到下一个询问区间。 离线算法，不带修复杂度为 \(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的询问 莫队的基础题，先把莫队扔上去。 考虑莫队维护区间平方和，难道我们要像线段树一样维护一个区间和，再维护一个区间平方和吗？ 我都写莫队了，先把贡献删了，修改后再加回去就行。 代码 小清新人渣的本愿 看完这个题面，已经对日本轻小说产生刻板印象了，果咩。 莫队套 bitset 模板题。 这种抽象东西肯定要拿莫队维护，然后就上值域 bitset 维护。 加法就是平移，减法存一个 \(N-x\) 的值，然后推两下式子就也可以变成平移。（此时有两个 bitset） 乘法就可以直接分解质因数，反正是 \(\sqrt n\) 的。 #include #define ll long long #define B 213 using namespace std; const int N = 1e5+10; const int M = 1e5; bitset struct Q{ int op,l,r,x,id; bool operator < (const Q &a)const{ return (l/B==a.l/B) ? (l/B&1) ? r } }q[N]; int n,m,a[N],cnt[N]; bool ans[N]; void add(int x){ if(cnt[a[x]]==0) c1[a[x]]=c2[M-a[x]]=1; cnt[a[x]]++; } void del(int x){ cnt[a[x]]--; if(cnt[a[x]]==0) c1[a[x]]=c2[M-a[x]]=0; } 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=1;i<=m;i++){ cin>>q[i].op>>q[i].l>>q[i].r>>q[i].x;q[i].id=i; } sort(q+1,q+1+m); int l=1,r=0; for(int i=1;i<=m;i++){ while(l>q[i].l) add(--l); while(r while(l while(r>q[i].r) del(r--); if(q[i].op==1){ if((c1 & (c1< ans[q[i].id]=1; }else if(q[i].op==2){ if((c1 & (c2>>(M-q[i].x))).any()) ans[q[i].id]=1; }else{ for(int j=1;j*j<=q[i].x;j++){ if(q[i].x%j==0){ if(c1[j]&&c1[q[i].x/j]){ ans[q[i].id]=1; break; } } } } } for(int i=1;i<=m;i++){ cout << (ans[i] ? "hana" : "bi") << '\n'; } return 0; } 曼哈顿交易 论莫队与值域分块的适配度：100% ！ 虽然本题有奇技淫巧省去值域分块的技巧，但是没必要，复杂度上界不是这个。 对第 \(i\) 种股票开一个桶计数，定义为 \(cnt1_i\)，再对 \(cnt1_i\) 开个桶计数为 \(cnt2_i\) 。 然后莫队维护是简单的，查询也是平凡的，就是简单的跳块然后找到所属块后暴力。 #include #define ll long long #define B 345 using namespace std; const int N = 1e5+10; int n,m,a[N],b[N],len; struct Q{ int l,r,k,id; bool operator < (const Q &a)const{ return l/B==a.l/B ? (l/B)&1 ? r } Q(int _l=0,int _r=0,int _k=0,int _id=0):l(_l),r(_r),k(_k),id(_id){} }q[N]; int ans[N],l=1,r=0; int bel[N],L[N],R[N],cnt[N],sum[N],tot,cnt2[N]; void init(){ tot=(N-10-1)/B+1; for(int i=1;i<=N-10;i++){ bel[i]=(i-1)/B+1; } for(int i=1;i<=tot;i++){ L[i]=(i-1)*B+1; R[i]=min(i*B,N-10); } } void add(int x){ sum[bel[cnt[x]]]--; cnt2[cnt[x]]--; cnt2[++cnt[x]]++; sum[bel[cnt[x]]]++; } void del(int x){ sum[bel[cnt[x]]]--; cnt2[cnt[x]]--; cnt2[--cnt[x]]++; sum[bel[cnt[x]]]++; } int query(int k){ int x; for(x=1;x<=tot;x++){ if(k-sum[x]<=0) break; k-=sum[x]; } if(x==tot+1) return -1; for(int i=L[x];i<=R[x];i++){ if(k-cnt2[i]<=0) return i; k-=cnt2[i]; } return -1; } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); init(); cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i];b[i]=a[i]; } sort(b+1,b+1+n);len=unique(b+1,b+1+n)-b-1; for(int i=1;i<=n;i++){a[i]=lower_bound(b+1,b+1+len,a[i])-b;} for(int i=1,l,r,k;i<=m;i++){ cin>>l>>r>>k; q[i]=Q(l,r,k,i); } sort(q+1,q+1+m); for(int i=1;i<=m;i++){ while(l>q[i].l) add(a[--l]); while(r while(l while(r>q[i].r) del(a[r--]); ans[q[i].id]=query(q[i].k); } for(int i=1;i<=m;i++){ cout << ans[i] << '\n'; } return 0; } 军队 第二分块状物，个人感觉写 分块维护并查集 做法比第二分块难写。 考虑并查集内维护同色块的一个代表，就以第一次出现的为代表即可，将所有的同色块指向代表。 接下来考虑操作。 操作一： 散块直接将所在整块的颜色还原，然后暴力修改后重构即可。 整块分类讨论，没有 \(x\) 颜色不修改，没有 \(y\) 颜色替换，两色都有也是暴力还原后修改，复杂度参考势能分析。 以不同颜色数量为势能，两色都有的时候势能减一，只有 \(O(n)\) 种颜色，总复杂度 \(O(n\sqrt n)\) 操作二： 散块暴力遍历直接加。 给 \(x\) 颜色打 \(tag\)，然后对块内和加 \(cnt_x\times v\)。 操作三： 散块暴力遍历直接求和。 整块返回块内和。 然后代码非常的…… #include #define ll long long #define B 750 #define L(i) (i-1)*B+1 #define R(i) min(i*B,n) using namespace std; constexpr int N = 2.5e5+5; int n,m,col,c[N]; ll a[N]; struct Query{ int op,l,r,x; ll y; }q[N]; ll tag[N],ans[N],sum; int fa[N],cnt[N],pre[N],tot; int find(int x){return fa[x]==x ? x : fa[x]=find(fa[x]);} inline void init(const int &x){ sum=0; for(int i=1;i<=col;i++) tag[i]=fa[i]=pre[i]=cnt[i]=0; for(int i=L(x);i<=R(x);i++){ fa[i]=pre[c[i]] ? pre[c[i]] : (pre[c[i]]=i); cnt[c[i]]++; sum+=a[i]; } } inline void modify1(const int &id,const int &x,const int &y){ if(!pre[x]) return ; if(!pre[y]){ c[pre[x]]=y; swap(cnt[y],cnt[x]); swap(tag[y],tag[x]); swap(pre[y],pre[x]); return ; }else{ cnt[y]+=cnt[x];cnt[x]=0; for(int i=L(id);i<=R(id);i++) c[i]=c[find(i)]; for(int i=L(id);i<=R(id);i++){ if(c[i]==x) a[i]-=tag[y]-tag[x],c[i]=y; } fa[pre[x]]=pre[y];tag[x]=pre[x]=0; } } inline void modify2(const int &id,int l,int r,const int &x,const int &y){ int nl=L(id),nr=R(id); l=max(nl,l),r=min(nr,r); for(int i=nl;i<=nr;i++){ c[i]=c[find(i)]; if(c[i]==x || c[i]==y) a[i]+=tag[c[i]]; } for(int i=l;i<=r;i++){ if(c[i]==x) c[i]=y; } cnt[x]=cnt[y]=pre[x]=pre[y]=tag[x]=tag[y]=0; for(int i=nl;i<=nr;i++){ if(c[i]==x || c[i]==y){ fa[i]=pre[c[i]] ? pre[c[i]] : (pre[c[i]]=i); cnt[c[i]]++; } } } inline void update1(const int &x,const ll &v){ if(!cnt[x]) return ; tag[x]+=v; sum+=v*1ll*cnt[x]; } inline void update2(const int &id,int l,int r,const int &x,const ll &v){ int nl=L(id),nr=R(id); l=max(nl,l),r=min(nr,r); for(int i=l;i<=r;i++){ if(c[find(i)]==x) a[i]+=v,sum+=v; } } inline ll query1(){ return sum; } inline ll query2(const int &id,int l,int r){ int nl=L(id),nr=R(id); l=max(nl,l),r=min(nr,r); ll res=0; for(int i=l;i<=r;i++){ res+=a[i]+tag[c[find(i)]]; } return res; } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m>>col; tot=(n-1)/B+1; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>c[i]; for(int i=1;i<=m;i++){ int op,l,r,x=0,y=0;cin>>op>>l>>r; if(op<3) cin>>x>>y; q[i]={op,l,r,x,y}; } for(int be=1;be<=tot;be++){ init(be); int nl=L(be),nr=R(be); for(int i=1;i<=m;i++){ int op=q[i].op,l=q[i].l,r=q[i].r; if(nl>r || nr if(op==1){ int x=q[i].x,y=q[i].y; if(nl>=l && nr<=r) modify1(be,x,y); else modify2(be,l,r,x,y); }else if(op==2){ int x=q[i].x,y=q[i].y; if(nl>=l && nr<=r) update1(x,y); else update2(be,l,r,x,y); }else{ if(nl>=l && nr<=r) ans[i]+=query1(); else ans[i]+=query2(be,l,r); } } } for(int i=1;i<=m;i++){ if(ans[i]) cout << ans[i] <<'\n'; } return 0; } 其他 这里记一些 Trick 和 势能分析 证明。 区间操作，若 \(a_i>x\) 则使 \(a_i-x\to a_i\) 分两种情况讨论： \(2x\ge mx\), 那么全局最大值变为：\(mx=mx-x\) \(2x < mx\), 我们可以先令 \(\le x\) 的数 +x ，那么全局就都比 x 大了，此时给全局打一个减法 tag，全局最大值依然变为：\(mx=mx-x\) 。 区间操作，将区间所有 \(x\) 变成 \(y\) 分类讨论： 若没有 \(x\) 直接跳过，都是 \(O(1)\)。 若没有 \(y\) 直接swap，都是 \(O(1)\)。 若 \(x,y\) 都有，对整体考虑，每次操作散块可能会增加一种颜色，初始时有 \(n\) 种颜色，所以颜色总数是 \(O(n+m)\) 的。每次暴力重构散块是 \(O(\sqrt n)\)，所以我们只需要 \(O((n+m)\sqrt n)\) 的复杂度就能重构散块。 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 大分块系列题。