根号分治的核心思想是平衡。
板子题。很容易想到两种暴力：一是不做预处理，每次询问暴力查询，这样复杂度是 $\mathcal O(q\times \dfrac{n}{p})$。二是预处理每个池子的值，每次 $\mathcal O(1)$ 查询，复杂度为 $\mathcal O(np)$。
观察两个式子，由于 $q,n$ 同阶，结合以下两种算法，发现可以平衡一下 $p$ 的取值，只预处理 $p\leq \sqrt n$ 的 $p$ 的每个池子的取值，复杂度 $\mathcal O(n\sqrt n)$。当 $p>\sqrt n$ 时，暴力跳复杂度也是对的 $\mathcal O(q\sqrt n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
namespace WrongAnswer_90
{
int n,m,bl,a[150001],b[401][401];
void mian()
{
read(n,m),bl=sqrt(n);int x,y;char ch;
for(int i=1;i<=n;++i)
{
read(a[i]);
for(int p=1;p<=bl;++p)b[p][i%p]+=a[i];
}
for(int i=1;i<=m;++i)
{
cin>>ch;read(x,y);
if(ch=='A')
{
if(x<=bl)write(b[x][y],'\n');
else
{
int s=0;
for(int i=y;i<=n;i+=x)s+=a[i];
write(s,'\n');
}
}
else
{
for(int p=1;p<=bl;++p)b[p][x%p]+=y-a[x];
a[x]=y;
}
}
}
}
就这样，通过对某个值的取值的分类讨论，并恰当的划分分界点我们就得到了一个相对优秀的算法。
板子题*2 还是类似的板子题，只不过空间存不下。用到一个神奇 trick：对于相同的 $p$ 离线处理，这样时间复杂度不变，空间也是线性的。
一道类似又不类似的题CF547E Mike and Friends，由于是多串匹配，还是考虑建立 ACAM。
发现信息有可减性，直接离线差分，把询问挂在序列上，问题变为查询 $[1,r]$ 中是 $s_k$ 子串的串的个数。
经典结论：1. 子串是一个串的前缀的后缀。2. fail 树上祖先是后代的后缀。
所以查询即对于每一个前缀查询 $[1,r]$ 中有多少个串是它的后缀，把 $[1,k]$ 区间的所有串结尾位置的权值设成 $1$，这也等价于在 fail 树上查所有前缀代表的节点到根的链的权值之和。单点加，根链查值，可以转为区间(子树)加，单点查值。
但是这样复杂度是假的，树状数组维护的话是 $\mathcal O(n\log m+\sum s_k \log m)$，用根号加，$\mathcal O(1)$ 查的值域分块平衡一下可以做到 $\mathcal O(n\sqrt m+\sum s_k)$。
注意其中后半部分是查询的所有 $s_k$ 串的长度之和，这个东西的大小是没有保证的。观察一下，发现复杂度退化的原因是可能对一个很长的串多次以他为 $s_k$，每次都要扫一遍它的所有前缀。
这启发我们对于串的长度大小分治：对于 $length\leq B$ 的串像上面一样暴力查，复杂度是 $\mathcal O(n\sqrt m+qB)$。
对于长度大于 $B$ 的串，数量不会超过 $\dfrac{m}{B}$ 个。对于每个串分别处理。假设当前处理的是 $s_k$，我们考虑每个串对这个串的贡献，即查每个串在这个串中的出现次数。这个是好做的，还是用到上面的经典结论：对于 $s_k$ 的每个后缀的节点，权值设成 $1$，这样一个串 $s_i$ 在 $s_k$ 中的出现次数就是 $s_i$ 结尾的子树中的权值和，$\mathcal O(n)$ 扫一遍，然后做一下前缀和。这样总复杂度是 $\mathcal O(n\sqrt m+qB+n\times \dfrac{m}{B})$，因为 $n,m,q$ 同阶，所以当 $B$ 取 $\sqrt n$ 时复杂度为 $\mathcal O(n\sqrt n)$。
过掉不难，但是想 $\mathcal O(n\sqrt n)$ 还是有一些思维含量的。
首先有一种暴力：预处理两两颜色间的答案，$\mathcal O(1)$ 查询。首先枚举颜色数，然后每种颜色 $\mathcal O(n)$ 扫一遍，这样预处理的复杂度是 $\mathcal O(n\times \mathrm{处理的颜色数})$。直接硬预处理显然过不去，所以可以考虑对出现次数较多的颜色预处理。设块长为 $B$，出现次数大于 $B$ 的颜色称为大块，否则为小块。
对于大块与大块，大块与小块，小块与大块之间的答案还是想上面一样预处理，预处理复杂度是 $\mathcal O(n\times \dfrac{n}{B})$。
对于小块，内部点数是 $\mathcal O(B)$ 级别的，树上的祖先后代问题用 dfn 序转化为区间问题：
$\sum_{i\in col_x}\sum_{j\in col_y}[in_i\leq dfn_j\leq out_i]$
直接做有 $in,out$ 两个限制，但是一个 $dfn$ 不可能即 $>out_i$ 有 $<in_i$，所以可以容斥一下，用总的点对数减去不合法的点对数，问题变为
$\sum_{i\in col_x}\sum_{j\in col_y}[dfn_j<in_i]$
可以树状数组做到 $B\log n$，但是更优秀的做法是预处理排序好的 $in$ 和 $dfn$，用类似归并排序求逆序对的思路双指针解决，对于 $>out_i$ 的部分也是同理。
总复杂度 $\mathcal O(n\times \dfrac{n}{B}+nB)$，$B$ 取 $\sqrt n$ 时复杂度为 $\mathcal O(n\sqrt n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int n,m,q,cnt,B=360,tot,dfn[200001],nfd[200001],pos[200001],sum[200001],a[200001],head[200001],to[200001],nex[200001],siz[25001],ans1[160][25001],ans2[160][25001];
inline void add(int x,int y){to[++cnt]=y,nex[cnt]=head[x],head[x]=cnt;}
vector<int> larg,ve[25001],ve2[25001];
void dfs(int k){dfn[k]=++tot;for(int i=head[k];i;i=nex[i])dfs(to[i]);nfd[k]=tot;}
void dfs1(int k){for(int i=head[k];i;i=nex[i])dfs1(to[i]),sum[k]+=sum[to[i]];}
void dfs2(int k){for(int i=head[k];i;i=nex[i])sum[to[i]]+=sum[k],dfs2(to[i]);}
inline bool cmp(int x,int y){return dfn[x]<dfn[y];}
inline bool cmp2(int x,int y){return nfd[x]<nfd[y];}
inline void mian()
{
cin>>n>>m>>q>>a[1],++siz[a[1]],ve[a[1]].eb(1);int x,y;
for(int i=2;i<=n;++i)cin>>x>>a[i],++siz[a[i]],ve[a[i]].eb(i),add(x,i);
for(int i=1;i<=m;++i)if(siz[i]>B)pos[i]=larg.size(),larg.eb(i);
dfs(1);
for(int i=1;i<=m;++i)ve[i].eb(0),ve2[i]=ve[i],sort(ve2[i].begin(),ve2[i].end(),cmp2),sort(ve[i].begin(),ve[i].end(),cmp);
for(int i=0;i<larg.size();++i)
{
for(auto j:ve[larg[i]])++sum[j];
dfs1(1);
for(int j=1;j<=n;++j)ans1[i][a[j]]+=sum[j];
memset(sum,0,sizeof(sum));
for(auto j:ve[larg[i]])++sum[j];
dfs2(1);
for(int j=1;j<=n;++j)ans2[i][a[j]]+=sum[j];
memset(sum,0,sizeof(sum));
}
while(q--)
{
cin>>x>>y;
if(pos[x])cout<<ans2[pos[x]][y]<<endl;
else if(pos[y])cout<<ans1[pos[y]][x]<<endl;
else
{
int ans=siz[x]*siz[y];
for(int i=1,j=1;i<=siz[x]&&j<=siz[y];++j)
{
while(i<=siz[x]&&dfn[ve[x][i]]<=dfn[ve[y][j]])++i;
ans-=siz[x]-i+1;
}
for(int i=siz[x],j=siz[y];i>0&&j>0;--j)
{
while(i>0&&nfd[ve2[x][i]]>=dfn[ve[y][j]])--i;
ans-=i;
}
cout<<ans<<endl;
}
fflush(stdout);
}
}
CF1039D You Are Given a Tree sol
神奇套路，对答案根分。大致发现答案和链长度是成反比的关系，所以对于较小的 $k$ 暴力计算，对于较大的 $k$ 通过枚举答案，然后二分找出对应的一段连续区间覆盖。