化德网站建设,网站开发任务,长春网易网站建设,百度网盘电脑版官网正题
题目链接:https://www.luogu.com.cn/problem/P6466 题目大意
给出kkk个长度为nnn的有序序列#xff0c;qqq次询问给出xxx#xff0c;求所有序列中xxx的后继的异或和。
强制在线 1≤k≤100,1≤n≤104,1≤q≤51051\leq k\leq 100,1\leq n\leq 10^4,1\leq q\leq 5\times…正题
题目链接:https://www.luogu.com.cn/problem/P6466 题目大意
给出kkk个长度为nnn的有序序列qqq次询问给出xxx求所有序列中xxx的后继的异或和。
强制在线
1≤k≤100,1≤n≤104,1≤q≤5×1051\leq k\leq 100,1\leq n\leq 10^4,1\leq q\leq 5\times 10^51≤k≤100,1≤n≤104,1≤q≤5×105 解题思路
一个很神奇的算法考虑如果我们将一个序列的偶数位提取出来我们得到在这些偶数位中xxx的后继的话那么原来序列中的后继中的距离不会超过111。
所以我们可以得到一个算法考虑原来的序列为aia_iai开始取出bkakb_ka_kbkak然后对于iii从k−1k-1k−1到111将bi1b_{i1}bi1的偶数位提取出来和aia_iai合并成一个新的有序bib_ibi。
那么求解时我们就可以只需要查询b1b_{1}b1中的后继了。
时间复杂度O(nkq(klogn))O(nkq(k\log n))O(nkq(klogn)) code
#includecstdio
#includecstring
#includealgorithm
#includecctype
using namespace std;
const int K110,N2e410;
int n,k,q,d,b[K][N],c[K][N];
int nxt[K][N],p[K][N],l[K];
inline int read(){int x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-f;cgetchar();}while(isdigit(c))x(x1)(x3)c-48,cgetchar();return x*f;
}
void print(int x)
{if(x9)print(x/10);putchar(x%1048);return;}
int main()
{nread();kread();qread();dread();for(int i1;ik;i){for(int j1;jn;j)b[i][j]read();}for(int i1;in;i)c[k][i]b[k][i];l[k]n;for(int ik-1;i1;i--){int z2;for(int j1;jn;j){while(zl[i1]c[i1][z]b[i][j]){c[i][l[i]]c[i1][z];p[i][l[i]]z;nxt[i][l[i]]b[i][j];z2;}c[i][l[i]]b[i][j];}while(zl[i1]){c[i][l[i]]c[i1][z];p[i][l[i]]z;z2;}for(int jl[i],lastl[i1];j1;j--)if(p[i][j])lastp[i][j];else nxt[i][j]-last;}int las0;for(int z1;zq;z){int x,ans0,i1;xread();x^las;int poslower_bound(c[1]1,c[1]1l[1],x)-c[1];ans^p[i][pos]?nxt[i][pos]:c[i][pos];while(ik){posp[i][pos]?p[i][pos]:-nxt[i][pos];pos--;i;while(posl[i]c[i][pos]x)pos;ans^p[i][pos]?nxt[i][pos]:c[i][pos];}lasans;if(z%d0)print(ans),putchar(\n);}return 0;
}
