BZOJ
比较裸。
第一眼以为\(n,m\le1000\)。。。
然后发现\(n\le1000,m\le300000,q\le500\)。
那么应该是个\(O(nq\log m)\)复杂度的算法了。\(\log^2m\)估计过不了。
因为\(m\)这一维非常大，所以我们考虑对\(y\)数组建可持久化01Trie。
然后每次询问，我们把\(x\)数组中的在询问范围内的拿出来（称之为询问\(x\)数组）。
从高位往低位贪心，每次在当前节点上遍历所有询问\(x\)数组，看一下01Trie上跟它异侧的\(y\)有多少个，然后判断当前位应该是\(0\)还是\(1\)，然后暴力把询问\(x\)数组的元素往下跳就行了。
#include<bits/stdc++.h>
#define pi pair<int,int>
#define fi first
#define se second
using namespace std;
namespace IO
{
char ibuf[(1<<21)+1],obuf[(1<<21)+1],st[15],*iS,*iT,*oS=obuf,*oT=obuf+(1<<21);
char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
void Flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
void Put(char x){*oS++=x;if(oS==oT)Flush();}
int read(){int x=0,c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}
void write(int x){int top=0;if(!x)Put('0');while(x)st[++top]=(x%10)+48,x/=10;while(top)Put(st[top--]);Put('\n');}
}
using namespace IO;
const int N=1007,M=300007;
int n,m,a[N],root[M],cnt,sum[M<<5],ch[M<<5][2];pi pos[N];
void insert(int &p,int pre,int x)
{
sum[p=++cnt]=sum[pre]+1;
for(int i=30,t=p,d;~i;--i) d=x>>i&1,ch[t][!d]=ch[pre][!d],pre=ch[pre][d],sum[t=ch[t][d]=++cnt]=sum[pre]+1;
}
void query(int l,int r,int pre,int p,int k)
{
int ans=0;
for(int i=l;i<=r;++i) pos[i]=pi(pre,p);
for(int i=30,j,s,x,f;~i;--i)
{
for(s=0,j=l;j<=r;++j) x=a[j]>>i&1,s+=sum[ch[pos[j].se][!x]]-sum[ch[pos[j].fi][!x]];
if(k<=s) ans|=1<<i,f=1; else k-=s,f=0;
for(j=l;j<=r;++j) x=(a[j]>>i&1)^f,pos[j].fi=ch[pos[j].fi][x],pos[j].se=ch[pos[j].se][x];
}
write(ans);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=m;++i) insert(root[i],root[i-1],read());
for(int Q=read(),u,v,l,r,k;Q;--Q) u=read(),v=read(),l=read(),r=read(),k=read(),query(u,v,root[l-1],root[r],k);
return Flush(),0;
}BZOJ
什么叫国际思维题啊。
首先我们知道这个字符串中出现的数就是给出的那\(n+1\)个数去掉\(0\)。
然后我们有一个想法：排序后第一个字符串的开头是\(0\)，这样我们就可以确定了\(0\)和第一个字符串末尾数字的相对关系。。。。这样我们总共可以确定\(n+1\)对相对关系。
此时如果数字都不重复的话我们就可以直接得到答案了，但是数字是有重复的，我们不知道我们和具体哪一个数字有相对关系。。。
现在我们来解决这个问题。
我们知道题目给我们的顺序就是字典序升序。
所以我们以字符串末尾的数字为第一关键字，题目给的顺序（这个数后面的数开头的字符串的字典序）为第二关键字排序，就能够得到以每个数开头的字符串的字典序。
这个东西和后缀数组里面的那个原理极为相似。
现在我们把所有字符串按字典序排序，并且知道它的第一个数字，又知道以这个数后面一个数开头的字符串的字典序。那么我们直接跳就完事了。
#include<bits/stdc++.h>
using namespace std;
int read(){int x=0,c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c))x=x*10+c-48,c=getchar();return x;}
#define pi pair<int,int>
#define x first
#define y second
pi a[200007];
int main()
{
int i,p,n=read();read();
for(i=0;i<=n;++i) a[i]=pi(read(),i);
sort(a,a+n+1),p=a[0].y;
for(i=1;i<=n;++i) printf("%d ",a[p].x),p=a[p].y;
}原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12008234.html