题解 P6466 【分散层叠算法(Fractional Cascading)】
小柯
2020-08-18 10:06:03
题意：
给定 $k$ 个序列，$q$ 次询问每个序列里 $x$ 的后继。
首先，~~本蒟蒻并没有学过分散层叠算法，于是去百度，又看不懂，再去 OIWiki ，又没有...于是决定自己想该怎么做...（主要是看到这道紫题还没有题解）~~
如果还是把所有序列分开处理的话，是很难突破 $O(klogn)$ 的下界的（二分查找），因为这是强制在线的。
所以考虑将这 $k$ 个序列归并到一起，形成一个序列 $A$。
归并的时候可以采用胜/败者树提高效率，当然也可以全部丢掉一起基数排序一下，所以预处理只需要 $O(nk)$。
考虑询问 $x$ 在每个序列里的后继，很明显，如果只要 $A$ 里面的值是远远不够的，还应该知道每个值原来是属于哪个序列的。所以预处理的时候维护另一个序列 $B$，表示 $A_i$ 是属于第 $B_i$ 个序列的。
继续考虑询问 $x$，首先肯定能在 $A$ 序列中找到一个位置 $pos$，使得 $A_{pos}$ 为 $x$ 的后继（如果有解的话），那么每个序列里 $x$ 的后继在 $A$ 序列里都应该在 $pos$ 后面。
于是考虑从 $pos$ 处逐一往后找，直到找齐 $1$ ~ $k$ 的 $B_i$ ，再将对应的 $A_i$ 异或起来即可。
在数列非常均匀的情况下，大约 $k$ 次就能找齐。但是数列如果不均匀，可能退化成 $nk$ 次，所以考虑优化。
如果要从前往后逐一找 $k$ 个确定的目标，那么可以考虑维护指针，以直接跳到该位置。所以维护 $nxt_{i,j}$ 表示 $i$ 后面第一个 $B_x$ 为 $j$ 的 $x$。那么一旦确定 $pos$，那么只需要访问 $A_{nxt_{pos,1}},A_{nxt_{pos,2}},A_{nxt_{pos,3}}...$ 即可找齐 $k$ 个原序列里的后继。
但是这样做有一个问题，也就是预处理 $nxt_{i.j}$ 空间复杂度和时间复杂度都有可能吃不消，那就放弃这个算法？不，考虑冗余在哪里。
很明显 $nxt_{i,j}$ 与 $nxt_{i+1,j}$ 有很大程度上可能是相同的，也就是说 $nxt$ 中存在大量的重复，那么是否可以减少 $nxt_i$ 存储的 $j$ 呢？答案是肯定的。
定义 $Nxt_i$ 表示 $nxt_{i,i\%k+1}$ ，那么显然，将 $Nxt_{i+k-1}$ ~ $Nxt_i$ 凑起来，就能得到 $nxt_i$。但是有个问题，有可能 $A_i$ ~ $A_{i+k-1}$ 被漏掉了，那么解决方法也很简单，考虑 $A_{Nxt_i}$ ~ $A_{Nxt_{i+k-1}}$ 的时候，同时也考虑 $A_i$ ~ $A_{i+k-1}$ ，总之，先到先得即可。
单次询问的复杂度为 $O(log(nk)+k)$。
所以最终复杂度为 $O(nk+qlog(nk)+qk)$，空间复杂度为 $O(nk)$，~~好像和分散层叠算法的时间复杂度和空间复杂度一样？~~
最后，放一下代码:
```cpp
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
#define INF 999999999
using namespace std;
int k,n,q,d;
int lastans,x;
int a[105][20005];
int A[2000005];
int B[2000005];
int nxt[2000005];
//此处nxt[i]的含义为原文的A[Nxt[i]]，主要是为了方便
int num[105];
//预处理nxt时用的临时数组
int rest[105];
//rest[i]表示每次询问的时候第i个原序列的后继是否已经找到
struct node{
int x,y,z;
node(){}
node(int _x,int _y,int _z):
x(_x),y(_y),z(_z){}
}now;
bool operator <(node a,node b){
return a.x>b.x;
}
priority_queue<node>Q;
int main(){
scanf("%d%d%d%d",&n,&k,&q,&d);
for(int i=1;i<=k;a[i][n+1]=INF,i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);
//在a[i][n+1]处放个极大值是为了避免等下归并的时候出现特殊情况
for(int i=1;i<=k;i++)Q.push(node(a[i][1],i,1));
for(int i=1;i<=n*k;i++){
now=Q.top();Q.pop();
A[i]=now.x,B[i]=now.y;
Q.push(node(a[now.y][now.z+1],now.y,now.z+1));
}
//这里的归并懒得用胜者树，直接用堆，但是用基排才是正确的复杂度，不过既然不会TEL，用堆更方便（
for(int i=n*k;i;i--){ //注意倒序枚举i，因为求的是后继
num[B[i]]=A[i];
nxt[i]=num[i%k+1];
}
for(int i=1;i<=q;i++){
scanf("%d",&x);x^=lastans;
lastans=0;
for(int j=1;j<=k;j++)rest[j]=0; //注意清零
int pos=lower_bound(A+1,A+n*k+1,x)-A; //lower_bound大法好！
for(int j=pos;j<pos+k&&j<=n*k;j++){
if(!rest[B[j]])rest[B[j]]=A[j]; //考虑A[i]~A[i+k-1]
if(!rest[j%k+1])rest[j%k+1]=nxt[j]; //考虑A[Nxt[i]]~A[Nxt[i+k-1]]
}
for(int j=1;j<=k;j++)lastans^=rest[j]; //计算答案
if(i%d==0)printf("%d\n",lastans);
}
return 0;
}
```
立个 flag，一定要学会分散层叠算法（
（我学了半天就学会了划分树/kk）