这题一开始写的线段数是从中间开始查找 k个 导致是nlogn 每次查找应该都是从头找每次找的个数不同就好了

还有一种递推的写法我放下面了

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 3e6+5;

const int MOD = 1e9+7;

int N,K,Q;

int ans[MAXN];

int turn[MAXN];

int dp[MAXN];

int a[MAXN];

int main(){

	int T; scanf("%d",&T);

	while(T--) {

		scanf("%d %d %d",&N,&K,&Q);

		int tt = N;

		int tot = 0;

		turn[0] = 0;

		while(tt) {

			++tot;

			turn[tot] = turn[tot-1] + (tt-1) / K + 1;

			tt = tt-1-(tt-1)/K;

		}

		for(int i = 0; i < N; ++i) {

			dp[i] = i%K? dp[i - i/K -1]+1 : 0;

			a[i]  = i%K? a[i - i/K -1] : i/K+1;

		}

		for(int i = 0; i < N; ++i) {

			int tmp = turn[dp[i]] + a[i];

			ans[tmp] = i+1;

		}

		for(int i = 0; i < Q; ++i) {

			int a; scanf("%d",&a);

			printf("%d\n",ans[a]);

		}

	}

	return 0;

}

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

const int MAXN = 3e6+5;

int N,K,Q;

int tree[MAXN<<2];

int st[MAXN];

void Build(int l,int r,int rt){

	tree[rt] = r-l+1;

	if(l == r) {

		return;

	}

	int m = (l+r)>>1;

	Build(lson); Build(rson);

}

int Ed;

void Find(int sum,int l,int r,int rt) {

	if(l == r) {

		tree[rt] = 0; Ed = r; return;

	}

	int m = (l+r) >>1;

	if(tree[rt<<1] >= sum) Find(sum,lson);

	else Find(sum-tree[rt<<1],rson);

	tree[rt] = tree[rt<<1] + tree[rt<<1|1];

}

int main(){

	int T; scanf("%d",&T);

	while(T--){

		memset(tree,0,sizeof(tree));

		scanf("%d %d %d",&N,&K,&Q);

		Build(1,N,1);

		int sz = N; int cnt = 0;

		while(sz>0) {

			int mx = (sz-1)/K;

			for(int i = 0; i <= mx; ++i) {

				int sum = 1+i*K-i;

				Find(sum,1,N,1);

				st[++cnt] = Ed; sz--;

			}

		}

		for(int i = 1; i <= Q; ++i){

			int a; scanf("%d",&a);

			printf("%d\n",st[a]);

		}

	}

	return 0;

}