根号分治学习笔记

根号分治的核心思想是平衡。

板子题。很容易想到两种暴力：一是不做预处理，每次询问暴力查询，这样复杂度是 \(\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)\)。

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\) 离线处理，这样时间复杂度不变，空间也是线性的。

CF587F Duff is Mad

一道类似又不类似的题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)\)。

P5901 [IOI2009] Regions 做完再写