贪心、二分、枚举倍数

题没读懂，诅咒出题人了。

给定长度为 $n$ 的序列 $a$，询问 $q$ 次，每次给定一个 $x$，可以进行任意次如下操作。

• 将一个不小于 $x$ 的 $a_i$ 减去 $x$。

最小化操作后 $a$ 的中位数，注意当 $n$ 为偶数时中位数为中心两个元素中较大的那个。

容易发现答案为模 $x$ 意义下序列的中位数，难点在于如何计算。注意到值域限制 $a_i \leq n$，而询问次数 $q$ 与 $n$ 同阶。对同一个序列多次询问相同的 $x$ 没有意义，所以最坏情况下应该是 $x$ 从 $1$ 到 $n$ 被问了一遍。

对于每个 $x$ 二分答案后枚举 $x$ 的所有倍数，因为 $x$ 将值域切割成了若干区间，每个区间都只有一段前缀对答案有贡献，使用前缀和快速求出每个区间的前缀贡献。预处理 $x \in [1,n] \cap \mathbb{Z}$ 的所有答案即可。

整体时间复杂度 $O(n \log ^2 n)$。

#include<bits/stdc++.h>
using namespace std;
int n,q,med,ans[100'005],sum[100'005];
int calculate(int x){
    int l=0,r=x-1,ret=x;
    while(l<=r){
        int mid=(l+r)>>1,cnt=sum[mid];
        for(int i=x;i<=n;i+=x) cnt+=sum[min(i+mid,n)]-sum[i-1];
        if(cnt<med) l=mid+1;
        else ret=mid,r=mid-1;
    }
    return ret;
}
void solution(){
    cin>>n>>q,med=(n+2-(n&1))/2;
    for(int i=1;i<=n;i++){
        static int x;
        cin>>x,++sum[x];
    }
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
    for(int i=1;i<=n;i++) ans[i]=calculate(i);
    for(int i=1;i<=q;i++){
        static int x;
        cin>>x;
        cout<<ans[x]<<" \n"[i==q];
    }
    for(int i=1;i<=n;i++) sum[i]=0;
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}