求中位数应经常联想到二分

题目链接：https://codeforces.com/contest/2008/problem/H

首先想了一会，随后想到了取模，但是由于这个q太大于是考虑是否可以实现动态变化最后还是没得出结果，遂看了题解。
原来这道题由于n的限制，所以可以对求出取模所对应的余数的取模区间
\([k*x,k*x+m]\)，于是复杂度到了\(nlogn\)（前缀和预处理），随后怎么去找这个中位数呢？二分！，然后复杂度
就到了\(n*logn*logn\)。联想到今年icpc网络赛的的一道求中位数的题，中位数的求法大概率是与中位数一起考察的，这点得牢记

#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll                                    long long 
#define lowbit(x) (x & -x)
using namespace std;
mt19937 rnd(time(0));
const ll mod=1e9+7;
const ll N=2e5+5;
ll ksm(ll x,ll y)
{
	ll ans=1;
	while(y)
	{
		if(y&1)
		ans=(ans%mod*x%mod)%mod;
		x=x%mod*(x%mod)%mod;
		y>>=1;
	}
	return ans%mod%mod;
}
ll gcd(ll x,ll y)
{
	if(y==0)
	return x;
	else 
	return gcd(y,x%y);
}
void fio()
{
		ios::sync_with_stdio(0);
		cin.tie(0);
		cout.tie(0);
}
ll a[2500000];
ll pre[2500000];
ll d[2500000];
bool vis[2500000];
int main()
{
	ll t;
	cin>>t;
	while(t--)
	{
	ll n,q;
	cin>>n>>q;
	map<ll,ll>f;
	for(ll i=1;i<=n;i++)cin>>a[i],f[a[i]]++;
	for(ll i=1;i<=n;i++)pre[i]=pre[i-1]+f[i],vis[i]=0,d[i]=0;//O(1)
	while(q--)
	{
		ll x;
		cin>>x;
		if(vis[x]>0)
		{
		cout<<d[x]<<" ";
		continue;
		}
		ll l=0,r=x-1;
		while(l<r)
		{
			ll mid=(l+r)>>1;
			ll ans=0;
		for(ll k=1;k*x<=n;k++)
		{
			ll l1=k*x;
			ll r2=min(k*x+mid,n);
			ans+=pre[r2]-pre[l1-1];
		}
		ans+=pre[mid];
		//<=mid的有
		//cout<<mid<<endl;
		//cout<<ans<<endl;
		if(ans>=n/2+1)
		{
			r=mid;
		}
		else l=mid+1;
		}
		cout<<r<<" ";
		d[x]=r;
		vis[x]=1;
	}
	cout<<endl;
	}

}