分散层叠算法(Fractional Cascading)

(Updated: )
(4 mins to read)

给定k个长度为n有序数组L，要求在线q次回答每个数组中$\geq x$的最小的数$k\leq 100,n\leq 10^4, q\leq 3\times 10^5$离线的话可以整体二分在线用该算法时间复杂度为$O(k+\log n)$，空间复杂度为$O(n)$用一个$k\times n$的二维数组M，M[i]的每一位记录三个信息，｛键值，在L[i]中后继的位置，在M[i+1]中后继的位置｝考虑从后往前构造，M[k]=L[k]由于是有序的，利用归并$O(n)$合并L[i]和M[i+1]，注意对于M[i+1]只合并偶数位置（节省空间）对于查询，先利用一次二分在M[1]中找到后继的位置，此时该位的第二个信息就表示了在L[1]数组中的答案，而该位的第三个信息表示了在M[2]中后继的位置，注意由于是间隔插入，所以需要和该位置的前一个位置取优。这样只需要一次二分，然后各数组间利用保存的信息（指针）可以$O(1)$转移

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
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define mp make_pair
using namespace std;
int main()
{
  int n, k, q, d;
  scanf("%d%d%d%d", &n, &k, &q, &d);
  vector<vector<int>> L(k, vector<int>(n));
  for(int i=0; i<k; i++)
    for(int j=0; j<n; j++)
      scanf("%d", &L[i][j]);
  vector<vector<pair<int,pair<int,int>>>> M(k);
  for(int i=0; i<n; i++)
    M[k-1].push_back(mp(L[k-1][i], mp(i, 0)));
  for(int i=k-2; i>=0; i--)
  {
    int a = 0, b = 1;
    while(a<n && b<sz(M[i+1]))
    {
      if(L[i][a]<=M[i+1][b].first) M[i].push_back(mp(L[i][a], mp(a, b))), a++;
      else M[i].push_back(mp(M[i+1][b].first, mp(a, b))), b += 2;
    }
    while(a<n) M[i].push_back(mp(L[i][a], mp(a, b))), a++;
    while(b<sz(M[i+1])) M[i].push_back(mp(M[i+1][b].first, mp(a, b))), b += 2;
  }
  int lstans = 0;
  for(int _=1; _<=q; _++)
  {
    int x; scanf("%d", &x);
    x ^= lstans;
    int p = lower_bound(M[0].begin(), M[0].end(), mp(x, mp(0, 0))) - M[0].begin();
    int curans = 0, idx = 0;
    while(idx<k && p<sz(M[idx]))
    {
      if(M[idx][p].second.first<n) curans ^= L[idx][M[idx][p].second.first];
      if(idx<k-1)
      {
        int nxtp = M[idx][p].second.second;
        if(nxtp-1<sz(M[idx+1]) && M[idx+1][nxtp-1].first>=x) --nxtp;
        p = nxtp;
      }
      ++idx;
    }
    lstans = curans;
    if(_%d==0) printf("%d\n", curans);
  }
  return 0;
}