正題

題目鏈接:https://www.luogu.com.cn/problem/P6466

---

題目大意

給出$k$個(gè)長度為$n$的有序序列，$q$次詢問給出$x$，求所有序列中$x$的后繼的異或和。

強(qiáng)制在線

$1\le k\le 100,1\le n\le 10^4,1\le q\le 5\times 10^5$

---

解題思路

一個(gè)很神奇的算法，考慮如果我們將一個(gè)序列的偶數(shù)位提取出來，我們得到在這些偶數(shù)位中$x$的后繼的話，那么原來序列中的后繼中的距離不會(huì)超過$1$。

所以我們可以得到一個(gè)算法，考慮原來的序列為$a_i$，開始取出$b_k=a_k$，然后對于$i$從$k?1$到$1$將$b_{i+1}$的偶數(shù)位提取出來和$a_i$合并成一個(gè)新的有序$b_i$。

那么求解時(shí)我們就可以只需要查詢$b_1$中的后繼了。

時(shí)間復(fù)雜度：$O(nk+q(k+\log n))$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; const int K=110,N=2e4+10; int n,k,q,d,b[K][N],c[K][N]; int nxt[K][N],p[K][N],l[K]; inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}while(isdigit(c))x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; } void print(int x) {if(x>9)print(x/10);putchar(x%10+48);return;} int main() {n=read();k=read();q=read();d=read();for(int i=1;i<=k;i++){for(int j=1;j<=n;j++)b[i][j]=read();}for(int i=1;i<=n;i++)c[k][i]=b[k][i];l[k]=n;for(int i=k-1;i>=1;i--){int z=2;for(int j=1;j<=n;j++){while(z<=l[i+1]&&c[i+1][z]<=b[i][j]){c[i][++l[i]]=c[i+1][z];p[i][l[i]]=z;nxt[i][l[i]]=b[i][j];z+=2;}c[i][++l[i]]=b[i][j];}while(z<=l[i+1]){c[i][++l[i]]=c[i+1][z];p[i][l[i]]=z;z+=2;}for(int j=l[i],last=l[i+1];j>=1;j--)if(p[i][j])last=p[i][j];else nxt[i][j]=-last;}int las=0;for(int z=1;z<=q;z++){int x,ans=0,i=1;x=read();x^=las;int pos=lower_bound(c[1]+1,c[1]+1+l[1],x)-c[1];ans^=p[i][pos]?nxt[i][pos]:c[i][pos];while(i<=k){pos=p[i][pos]?p[i][pos]:-nxt[i][pos];pos--;i++;while(pos<=l[i]&&c[i][pos]<x)pos++;ans^=p[i][pos]?nxt[i][pos]:c[i][pos];}las=ans;if(z%d==0)print(ans),putchar('\n');}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P6466-分散层叠算法(Fractional Cascading)【模板】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。