H. Sakurako's Test

onlyblues / 2024-09-03 / 原文

H. Sakurako's Test

Sakurako will soon take a test. The test can be described as an array of integers $n$ and a task on it:

Given an integer $x$, Sakurako can perform the following operation any number of times:

Choose an integer $i$ ($1\le i\le n$) such that $a_i\ge x$;
Change the value of $a_i$ to $a_i-x$.

Using this operation any number of times, she must find the minimum possible median$^{\text{∗}}$ of the array $a$.

Sakurako knows the array but does not know the integer $x$. Someone let it slip that one of the $q$ values of $x$ will be in the next test, so Sakurako is asking you what the answer is for each such $x$.

$^{\text{∗}}$The median of an array of length $n$ is the element that stands in the middle of the sorted array (at the $\frac{n+2}{2}$-th position for even $n$, and at the $\frac{n+1}{2}$-th for odd)

Input

The first line contains one integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $q$ ($1\le n,q\le 10^5$) — the number of elements in the array and the number of queries.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1\le a_i\le n$) — the elements of the array.

The following $q$ lines each contain one integer $x$ ($1\le x\le n$).

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$. The same guarantee applies to the sum of $q$ across all test cases.

Output

For each test case, output $q$ integers — the answer for each query.

Example

Input

2
5 5
1 2 3 4 5
1
2
3
4
5
6 3
1 2 6 4 1 3
2
1
5

Output

0 1 1 1 2 
1 0 2

解题思路

首先要知道当集合中的元素越小，那么集合中元素的中位数越小。因此我们应该让一个数尽可能减去 $x$，最后得到 $a_i := a_i \bmod x$。对于固定的 $x$，在执行操作后中位数就已经确定了，即第 $\lfloor \frac{n}{2} \rfloor + 1$ 小的数。但由于需要对每个 $a_i$ 模 $x$，直接暴力做的话时间复杂度是 $O(qn)$。

不妨换个思虑，对于每个 $x$ 二分出最小的中位数（初始时二分的左右端点分别为 $0$ 和 $x-1$），假设二分点为 $m$，那么余数不超过 $m$ 的元素个数如果至少为 $\lfloor \frac{n}{2} \rfloor + 1$，则说明中位数小于等于 $m$。因此现在问题是如何快速求出模 $x$ 后不超过 $m$ 的元素数量。

把每个元素看作是 $q \cdot x + r, \, (q \in \mathbb{N}, \, 0 \leq r <x)$ 的形式，因此满足模 $x$ 不超过 $m$ 的数可以表示成区间 $[k \cdot x, k \cdot x + m]$。由于 $a_i \leq n$，因此 $k \leq \lfloor \frac{n}{x} \rfloor$。枚举 $k$，累加值在 $[k \cdot x, k \cdot x + m]$ 内的元素数量（可以用权值前缀和作差得到），最后判断累加的值是否不小于 $\lfloor \frac{n}{2} \rfloor + 1$ 即可。

利用调和级数的性质，我们直接预处理出 $x \in [1, n]$ 的答案。时间复杂度就是 $\sum\limits_{x=1}^{n}{\frac{n}{x} \cdot \log{x}} \leq n \log^2{n}$。最后 $O(1)$ 查询即可。

AC 代码如下，时间复杂度为 $O(n \log^2{n})$：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1e5 + 5;

int n, m;
int s[N], ans[N];

bool check(int x, int m) {
    int cnt = 0;
    for (int i = 0; i <= n; i += x) {
        cnt += s[min(n, i + m)] - s[i - 1];
    }
    return cnt >= n / 2 + 1;
}

void solve() {
    cin >> n >> m;
    memset(s, 0, n + 1 << 2);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s[x]++;
    }
    for (int i = 1; i <= n; i++) {
        s[i] += s[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        int l = 0, r = i - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(i, mid)) r = mid;
            else l = mid + 1;
        }
        ans[i] = l;
    }
    while (m--) {
        int x;
        cin >> x;
        cout << ans[x] << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}