以碎片拼凑的世界，即为人之光辉。
分散层叠
一个很新的科技，结果被 lxl 用到了 里，兴致勃勃来刷大分块，就来学习一下这个算法，似乎是 年集训队论文提到过的，但在国外似乎早有普及，称为 ，中文译为分散层叠算法。
思想
我们以最经典的一道题来实现：
题目简介
题目名称：分散层叠算法
题目来源：未知
评测链接：https://www.luogu.com.cn/problem/P6466
形式化题意：给定 个长度为 的有序数组，一共有 次询问，给出 ，求出每个数组中 的非严格后继（不存在为 ），查询 个后继的异或和。强制在线。只需要输出编号为 的倍数的询问。保证 不重复，且每个数组严格递增。
数据范围：
首先考虑暴力，对于每一个数组，因为保证严格递增，所以可以每次询问做 次 std::lower_bound，时间复杂度 ，按照这个时间复杂度甚至卡卡常还能过。但显然，如果存在一个 的数据范围这铁定死惨。
那我们能不能根号分治一下？将 个序列归并到一起，然后预处理 在序列中的位置，用空间换时间，对于每个位置维护一个大小为 的集合表示这个位置 个序列的后继，这样可以做到单次询问 。但是空间复杂度 。
那很显然了，这道题当 很大时用前面的方法，否则用后面的方法就可以通过了。
那么我们使用分散层叠，可以用前面的时间和后面的空间以及在线的做法做这道题。
我们考虑构造 的新的序列 ，以对应 个原来的序列 ，构造方法如下：
- ；
- 由 与从 中每两个元素选择一个的子序列 归并。
中的每个位置存在一个二元组 ，其中 表示 对应 ，而 对应 。一个比较显然的是 一定是偶数。
如果 ，且 为：，那么我们得到的 序列为：
这一段的空间复杂度和时间复杂度为 ，可以称为线性。
然后考虑预处理了 后对我们的查询有什么帮助，我们首先在 中找到当前 的后继，然后通过 找到 的位置，然后前后匀一下判断答案是否合法。直到 ，时间复杂度 。你发现这其实就是通过一种奇妙的空间存储方式实现了上述那个 的做法。
但我们显然需要知道这是否正确。
考虑数学归纳法，显然 的答案一定正确，因为 所以二分出来和原答案没有区别。然后我们现在设 的 都正确，现在证明 的答案。 中除开 序列之外的元素是从 中以 的比例提取出来的，设当前 的答案为 ，而 一定是 的后继，而 在 的后继，与后继的后继中一定有一个存在在 中，所以 也肯定在这之间，所以 在 的后继也就在这 之中，而事实上，后继下标相差 。
这样下来，我们有了一个时间复杂度 ，时间复杂度 （有几倍常数）的算法。
至于怎么匀摊，直接写两个 while 往左往右就可以了。
参考实现
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
50
51
52
53
54
55
56
57
58
59
| int N,K,Q,D,lastans;
int val[MAXK][MAXN],Len[MAXK],M1[MAXN];
struct Array
{
int val,pos,nxt;
Array(int _v=0,int _p=0,int _n=0):val(_v),pos(_p),nxt(_n){}
}M[MAXK][MAXN],tmp[MAXN];
inline void build()
{
Len[K]=N;
for(int i=1;i<=N;++i) M[K][i]=Array(val[K][i],i,0);
for(int k=K-1;k>=1;--k)
{
int tot=0;
for(int i=1;i<=Len[k+1];++i) if(!(i&1)) tmp[++tot]=M[k+1][i],tmp[tot].nxt=i;
int cur=1,cur2=1;
for(int i=1;i<=N;++i)
{
while(cur<=tot&&tmp[cur].val<=val[k][i])
{
tmp[cur].pos=i;
M[k][++Len[k]]=tmp[cur];
++cur;
}
while(cur2<=Len[k+1]&&M[k+1][cur2].val<=val[k][i]) ++cur2;
M[k][++Len[k]]=Array(val[k][i],i,cur2);
}
while(cur<=tot)
{
tmp[cur].pos=N+1;
M[k][++Len[k]]=tmp[cur];
++cur;
}
}
for(int i=1;i<=Len[1];++i) M1[i]=M[1][i].val;
}
int main()
{
read(N,K,Q,D);
for(int k=1;k<=K;++k)
for(int i=1;i<=N;++i)
read(val[k][i]);
build();
for(int i=1,qx;i<=Q;++i)
{
read(qx),qx^=lastans;
int pos=std::lower_bound(M1+1,M1+Len[1]+1,qx)-M1,res=0;
for(int k=1;k<=K;++k)
{
while(pos<=Len[k]&&M[k][pos].val<qx) ++pos;
while(pos>=2&&M[k][pos-1].val>=qx) --pos;
if(pos<=Len[k]) res^=val[k][M[k][pos].pos],pos=M[k][pos].nxt;
else pos=Len[k+1]+1;
}
if(i%D==0) write(res,'\n');
lastans=res;
}
return 0;
}
|
应用
大概看了一下，一般用在 或者分块优化上。
分散层叠在图论上的应用
现在有一个 （有向无环图），保证每个点的度数不会超过 ，每个点上有一个序列 ，每次查询一条链上每个结点对应序列中 的后继。
你发现对于刚刚那道题而言，实际上就是 时， 为链的特殊情况。
这种推广的做法是将 的归并比例从 变成 ，需要归并的序列也就是 结点的所有后继，这样会使初始化时间复杂度变成 ，而查询时间复杂度为 。而这个 就是归并后继与真实后继的极差，分散层叠算法可以保证极差一定在 之内。又因为 是一个常数，所以我们一般认定查询时间复杂度不变。
分散层叠的实质便是通过误差扰动来处理本身精确而限制巨大的问题。而在例题中，这个扰动指数为 ，根据 的推导，我们发现，扰动指数越大，我们得到的预处理就越模糊，所需要的时间复杂度同样越小，但这样就会让查询变得更加不便，因为扰动指数变大后会让误差随之变大，所以就会增加查询的时间复杂度，这也是一种平衡规划，可以在一些题中通过均摊时间复杂度来做到奇效。
如果笔者有时间会进行一些学习。当然，如果读者感兴趣，也可以去阅读 年的集训队论文，里面有一篇对分散层叠做了专门的讲解。有提到，扰动指数为 时会对预处理造成 的影响，而会对查询造成 的影响。
更甚至，论文中提到有关带修情况下的分散层叠算法，支持动态插入，可以做到 的预处理-修改-查询时间复杂度。
分块优化
其实你认真去读他那篇论文，发现里面的例题全是 ，后来人也发现分散层叠专克大分块系列（甚至鸣谢还有 lxl 在里面），虽然 lxl 因为懒在出大分块的时候没有使用分散层叠，但大部分 在线段树分散层叠的优化下可以做到非常优美的时间复杂度。
区间加区间排名
题目简介
题目名称：由乃打扑克
题目来源：
评测链接：https://www.luogu.com.cn/problem/P5356
形式化题意：给定一个长度为 的序列以及 次操作：
数据范围：
分块做法在另外一篇博客（ 做题记录），这里主要说一下分散层叠在分块中的优化。
首先这是一道 的题，其次这是一道 题，熟悉 lxl 出题方式的人就会发现，这道题并没有强制在线，说明这道题有离线做法。
考虑离线后将两次修改间的所有询问统一处理，论文中提到了一种叫做 的数据结构，可以用来优化二分，但并不常用，也不实用。这里首先考虑在同一个块中实现多次二分。
在重构之前，我们可以将所有相关询问从小到大在归并同时进行处理，这里会利用单调性，就可以直接在 的时间内解决。而当值域为 时，可以直接以 为基底做基数排序，可以将时间复杂度优化到 ，最后可以做到 ，当 时，可以做到 。
但事实上，上述算法有值域限制，也就是必须保证有 才能够实现，但我们可以通过分散层叠优化最初的算法。
我们考虑取 的比例对块与块之间进行分散层叠，这样我们在块与块之间移动时偏差不会超过 ，让时间做到 。然后我们将 个块作为一组分散层叠，一共作 层。
然后考虑修改，注意到与普通修改一致，整块的修改不会影响元素相对性，所以分散层叠的元素也不会改变，所以至多 组分散层会被改变，重构分散层的时间复杂度为 。
通过分散层叠，查询的时间复杂度可以优化到每个分散层 ，一共 。而对于分散层外的块还需要 的时间二分，总共 。
所以单次操作的时间复杂度为 ，总时间复杂度为 ，而取 时做到最优复杂度 。
这道题还有更甚的优化，将分散层叠的思想用到线段树上，以较小的比例归并线段树结点的序列可以做到 ，取 时做到最优复杂度 ，但这个思想与分散层叠没有较大关联，感兴趣的读者可以自行在论文或洛谷题解中阅读。（实际上非常有关联，只是我不会而且没时间学）