[数据结构与算法]【模板】分散层叠算法（P6466）

正题

P6466

题目大意

给你 k 个大小为 n 的数组，有q次询问，每次询问回答x在k个数组中的后继的异或和

解题思路

分散层叠模板

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define K 110
#define N 20100
using namespace std;
int n,k,q,d,x,ans,len[K],a[K][N],b[K][N],fr[K][N],nx[K][N][2];
void pre()
{
	int x,y;
	for(int i=k;i>0;--i){
		x=1;
		y=2;
		while(x<=n||y<=len[i+1]){
			len[i]++;
			if(x<=n&&(a[i][x]<=b[i+1][y]||y>len[i+1])){
				b[i][len[i]]=a[i][x];
				nx[i][len[i]][0]=len[i];
				nx[i][len[i]][1]=n+len[i+1]/2+1;
				x++;
			}
			else{
				b[i][len[i]]=b[i+1][y];
				fr[i][len[i]]=y;
				nx[i][len[i]][0]=n+len[i+1]/2+1;
				nx[i][len[i]][1]=len[i];
				y+=2;
			}
		}
		for(int j=len[i]-1;j>0;--j)
			nx[i][j][1]=min(nx[i][j][1],nx[i][j+1][1]),nx[i][j][0]=min(nx[i][j][0],nx[i][j+1][0]);
		nx[i][len[i]+1][0]=nx[i][len[i]+1][1]=len[i]+1;
		fr[i][len[i]+1]=len[i+1]+1;
	}
	return;
}
int dfs(int x,int y,int z)
{
	if(x>k)return 0;
	if(y>1&&z<=b[x][y-1])y--;
	int s1=nx[x][y][0],s2=nx[x][y][1],now=0;
	if(s1<=len[x])now=b[x][s1];
	return now^dfs(x+1,fr[x][s2],z);
}
int ask(int x)
{
	if(x>b[1][len[1]])return dfs(1,len[1]+1,x);
	int l=1,r=len[1];
	while(l<r){
		int mid=l+r>>1;
		if(x<=b[1][mid])r=mid;
		else l=mid+1;
	}
	return dfs(1,l,x);
}
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]);
	}
	pre();
	for(int i=1;i<=q;++i){
		scanf("%d",&x);
		x^=ans;
		ans=ask(x);
		if(i%d==0)printf("%d\n",ans);
	}
	return 0;
}