分散层叠算法：优化多序列kth的NB武器

· · 题解

前言

wjc 那天有个分块题被我找到原题然后叉掉了。

没有做出来，然后去找了个题解。

翻了翻找到一篇 分散叠层加分块的 O(n \sqrt {nlog_n})题解，没想到此题还有如此优秀的复杂度？这分散叠层又是个什么玩意儿？抱着无聊的本质上网搜了一下发现可以用在一些题里面优化分块，就去学了学。

正文

P1 何为“分层”思想

就是字面意思。

分散层叠算法的英语为 Fractional Cascading，Fractional的意思是零碎的微小的，Cascade即小瀑布。其提出者这么命名，也许就是想说小瀑布会汇聚成大瀑布吧（ 。

用中文来说，小黄河汇聚成大黄河~，诶这都不重要，感性理解成把我们需要的东西拆成很多层,然后我们相邻的两层之间都有一些联系，可以是我们分散叠层中，利用前一个序列推向后一个序列的nxt指向方法，也可以是我们跳表中通过抽样缩小查询的分层方法……

P2 分散叠层到底是个什么东西

我们先来想一道题：现在有 k 个有序序列，每个序列长为 n ，且保证 nk \leq 2 \times 10 ^ 6 ，现在我们有 m 个数，我们对于每一个数，想要知道它在这 k 个序列中的非严格后继。

首先我们要裸一下，有序，后继，这不直接对每个序列二分一下不就好了，时间复杂度 O(mklog_n) ，你看这 O(mk) 啊，岂是可取之材？扔了扔了。

接着我们发现这个算法的唯一劣势就是时间复杂度太高了，我们为何不去优化一下呢？我们直接考虑暴力揉团团，把这 k 个序列揉成一个序列，对于大序列的每一个元素我们跟 k 个数字，第 i 个数字表示当我们二分查找大序列时，如果找到了当前这个元素，那么在第 i 个序列二分查找时对应的位置就应该是第 i 个数字，这个可以用 k 个序列进行归并 O(nk) 得到，时间复杂度 O(log_n + k) ，但是空间复杂度 O(nk ^ 2) 真的不敢恭维。

现在我们有了两个算法，一个时间爆炸一个空间爆炸，如果我们可以融合一下，诶这不就解决了？

为了更好说明，我们先来举一个例子，假如有 k 个序列，我们先令 L[i] 为第 i 个序列的原序列， M[i] 为第 i 个序列的新序列（后面会讲解这个 M 有什么用） 。

假设 k = 3 ，原序列分别为：

L[1] = {1 4 6 7 10 20}

L[2] = {2 3 8 11 14 18}

L[3] = {5 9 12 13 15 17}

现在，我们 M[i] 里面的元素都跟了两个数字 now[j] , nxt[j] ，第一个表示的是如若在 M[i] 里二分找到了当前的 M[i][j] ，那么在原 L[i] 序列里面二分应该找到 now[j] 这个位置，而在 M[i + 1] 里二分就应该找到 nxt[j] 这个位置。

我们从下往上依次处理每个 M[i] 序列，具体而言，我们如若得到 M[i + 1] 现在想要得到 M[i] ，我们就从 M[i + 1] 里面每隔一个元素就抽出来一个元素，然后和 L[i] 进行归并得到：

M[1] = {1[1,2],3[2,2],4[2,4],6[3,4],7[4,4],9[5,4],10[5,6],13[6,6],17[6,8],20[6,8]}

M[2] = {2[1,2],3[2,2],8[3,2],9[4,2],11[4,4],13[5,4],14[5,6],17[6,6],18[6,6]}

M[3] = {5[1,0],9[2,0],12[3,0],13[4,0],15[5,0],17[6,0]}

这里的从下往上处理过程也并不困难，我们首先可以得到 M[3] ，接着我们在归并时一个个往上面放即可，伪代码一下： 

pks.clear() ; v[i].push_back(pks);
int siz = v[i + 1].size() - 1 , l = 1 , ll = 1 , cnt = 0;
for(int j = 2 ; j <= siz ; j += 2) 
{
    Used[++ cnt] = v[i + 1][j];
    Used[cnt].now = j; 
}
while(l <= cnt && ll <= n)//这里的x对应的就是now[j],y就是nxt[j]
{
    if(Used[l].val < a[i][ll])
    {
        pks.val = Used[l].val , pks.y = Used[l].now , pks.x = ll;
        v[i].push_back(pks);
        l ++;
    }
    else 
    {
        pks.val = a[i][ll] , pks.y = Used[l].now , pks.x = ll;
        v[i].push_back(pks);
        ll ++;      
   }
}
while(l <= cnt){pks.val = Used[l].val , pks.y = Used[l].now , pks.x = ll; v[i].push_back(pks);l ++;}
while(ll <= n){pks.val = a[i][ll] , pks.y = Used[l - 1].now , pks.x = ll; v[i].push_back(pks);ll ++;}

如果我们要查询一个数时，我们只要在 M[1] 里面做一次二分，然后通过 nxt 数组找到 M[2] 里面对应的位置，只不过这时我们需要遍历一下前后看一下当前答案是否合法，接着我们在去 M_3…… 而每个 M[i] 数组里面找到的元素的第一维就是我们想要的答案，时间复杂度 O(log_n + k) 。
而空间复杂度呢？我们可以这么证明，由于每次我们都是折半取出，然后空间复杂度就是 O(1 + \frac{1}{2} + \frac{1}{4} + ……) = O(2n) ，空间复杂度也极其优秀。

证明了这个时空复杂度后，那为什么这个做法是对的呢？

我们可以很显然地使用数学归纳法证明，M[k] 的答案很显然是对的，那么我们在任意的 M[i + 1] 是正确的情况下，由于我们是从 M[i + 1] 里面以 \frac{1}{2} 的比例提取，所以假设 M[i + 1] 里的两个位置 pos , pos + 2 所以我们如若在 M[i] 里面找到一个数，如若它指向 pos + 2 的话，由于我们把 pos 插入进去了，所以答案肯定在 pos + 1 和 pos + 2 之间，这不就得证了？可以抽象理解成我们一段数的端点插入进去了，就自然而然把区间查找范围缩小到了一个程度，所以我们如果以 frac{1}{D} 的比例提取，那么我们在 M[i + 1] 里面还需要查询的区件长度就为 D ，所以说我们分散叠层的单次时间复杂度为 O(log_n + klog_D) ，只不过这个 D 我们选取时就已经很小了，这个 log_D 真的很鸡肋……

这样，这道题的分散叠层算法就到此结束。

接下来先附上模板题的代码，如果您仅限于模板题的学习可以到此为止了。

不过由于网上现在也没有一个成型的分散叠层算法的学习体系，所以这个模板是我自己打的……如果挂掉了评论区喷就好了。 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int Len = 2e4 + 5;
int n,k,q,d,a[105][10005];
struct node
{
    int x,y,val,now;
    inline void clear(){x = 0 , y = 0 , val = 0;}
}pks;
node Used[20005];
vector<node> v[105];
void Init()
{
    pks.clear() ; v[k].push_back(pks);
    for(int j = 1 ; j <= n ; j ++) 
    {
        pks.x = j , pks.y = 0;
        pks.val = a[k][j];
        v[k].push_back(pks);
    }
    for(int i = k - 1 ; i >= 1 ; i --)
    {
        pks.clear() ; v[i].push_back(pks);
        int siz = v[i + 1].size() - 1 , l = 1 , ll = 1 , cnt = 0;
        for(int j = 2 ; j <= siz ; j += 2) 
        {
            Used[++ cnt] = v[i + 1][j];
            Used[cnt].now = j; 
        }
        while(l <= cnt && ll <= n)
        {
            if(Used[l].val < a[i][ll])
            {
                pks.val = Used[l].val , pks.y = Used[l].now , pks.x = ll;
                v[i].push_back(pks);
                l ++;
            }
            else 
            {
                pks.val = a[i][ll] , pks.y = Used[l].now , pks.x = ll;
                v[i].push_back(pks);
                ll ++;
            }
        }
        while(l <= cnt){pks.val = Used[l].val , pks.y = Used[l].now , pks.x = ll; v[i].push_back(pks);l ++;}
        while(ll <= n){pks.val = a[i][ll] , pks.y = Used[l - 1].now , pks.x = ll; v[i].push_back(pks);ll ++;}
    }
} 
int Find(int Ins)
{
    int l = 1 , r = v[1].size() - 1 , pos = 0 , res = 0 , to;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(v[1][mid].val >= Ins) pos = mid , r = mid - 1;
        else l = mid + 1;
    }
    if(!pos) res ^= 0 , pos = v[1].size() - 1;
    else res ^= a[1][v[1][pos].x];
//  printf("%d\n",a[1][v[1][pos].x]);
    to = v[1][pos].y;
    for(int i = 2 ; i <= k ; i ++)
    {
        int siz = v[i].size() - 1;
        if(to >= 2 && v[i][to - 1].val >= Ins) to --;
        else if(v[i][to].val < Ins && to + 1 <= siz && v[i][to + 1].val >= Ins) to ++;
        else if(to + 1 <= siz && v[i][to + 1].val <= Ins) to ++;
        if(to == siz && v[i][to].val < Ins) 
            res ^= 0 , to = v[i][to].y;
        else res ^= a[i][v[i][to].x] , to = v[i][to].y ;

    }
    return res;
} 
int main()
{
    scanf("%d %d %d %d",&n,&k,&q,&d);
    for(int i = 1 ; i <= k ; i ++) 
        for(int j = 1 ; j <= n ; j ++) scanf("%d",&a[i][j]);
    Init();
    int lstans = 0;
    for(int i = 1 ; i <= k ; i ++)
    {
        int siz = v[i].size() - 1;
        for(int j = 1 ; j <= siz ; j ++) printf("%d[%d,%d],",v[i][j].val,v[i][j].x,v[i][j].y);
        puts("");
    }
    for(int i = 1 ; i <= q ; i ++)
    {
        int Ins;scanf("%d",&Ins);
        Ins ^= lstans;
        lstans = Find(Ins);
        if(i % d == 0) printf("%d\n",lstans);
    }
    return 0;
}

P3 分散叠层算法的普遍现象

这里我们可以把这个题目抽象一下，假如我们有一个 DAG ，这个 DAG 上的每个点都有一个有序序列，且每个点的入度出度在常数 d 之内现在我们想对任意的一个路径查询，我们模板题的一个问题。

很明显，这里的分散叠层得变一下，我们发现其实大体框架还是没变，变的只是我们的选取比例 \frac{1}{D} ，这里其实就得结合题目了，去尽量均衡时空复杂度即可。

设路径长为 len 。

单次时间复杂度 O(log_n + len log_D)

空间复杂度为 O(nd) 。

这里可能也不是很严谨，具体的可以再参考一下 20年集训队论文，蒋明润《浅谈利用分散层叠算法对经典分块问题的优化》 。

P4 一些个人感想

分散叠层的实用性其实确实不好，而且有点难码，一般还是很难运用到题目中，不过其思想还是有很多运用在了当今 OI 领域，例如跳表，Range Tree ……

总的来说，冲这个思想，你说他难又不难，还挺好理解的，还是很有价值的一个算法。