用线段树可以算出序列。然后o(1)询问。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } template <class T> inline void read(T &x) { char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } } const int maxn=3000010; int T,n,k,q,sz,cnt,p; int s[4*maxn],ans[maxn]; void build(int l,int r,int rt) { s[rt]=0; if(l==r){ s[rt]=1; return;} int m=(l+r)/2; build(l,m,2*rt); build(m+1,r,2*rt+1); s[rt]=s[2*rt]+s[2*rt+1]; } void get(int sum,int l,int r,int rt) { if(l==r) { s[rt]=0, p=l; return; } int m=(l+r)/2; if(s[2*rt]>=sum) get(sum,l,m,2*rt); else get(sum-s[2*rt],m+1,r,2*rt+1); s[rt]=s[2*rt]+s[2*rt+1]; } int main() { // File(); scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&k,&q); build(1,n,1); sz=n; cnt=0; while(sz>0) { int mx=(sz-1)/k; for(int i=0;i<=mx;i++) { int sum=1+i*k-i; get(sum,1,n,1); ans[++cnt]=p; sz--; } } for(int i=1;i<=q;i++) { int x; scanf("%d",&x); printf("%d ",ans[x]); } } return 0; }