AT_abc255_d [ABC255D] ±1 Operation 2

思路

因为 $1 \leq n,q \leq 2 \times 10^5$，所以对于每一次查询的时间复杂度一定要达到 $\Theta(\log n)$，甚至于 $\Theta(1)$。

一个最简单的想法，我们先统计出整个序列 $a$ 的和 $sum$，然后答案是 $|sum - x \times n|$。

很显然，这个想法是错误的，因为对于 $a$ 中只有两个元素 $x - 1,x + 1$ 的时候，这样算出来答案为 $0$，但是，这种情况答案应该是 $2$。

那么，换一个思路。

不难发现，对于一个数 $a_i$，它的操作次数满足如下 $3$ 个结论：

1. 当 $a_i < x$ 时，将操作 $x - a_i$ 次。
2. 当 $a_i = x$ 时，将操作 $0$ 次。
3. 当 $a_i > x$ 时，将操作 $a_i - x$ 次。

那么，我们不妨令序列 $b$ 中存储了 $a$ 中小于 $x$ 的元素，$c$ 中存储了 $a$ 中大于 $x$ 的元素。

很显然，答案就是（$B,C$ 分别为 $b,c$ 中的元素个数）：

$$\sum_{i = 1}^{B}{b_i} + \sum_{i = 1}^{C}{c_i}$$

因此，现在的问题就转化为了求 $b$ 和 $c$。

我们发现，对于此题，打乱 $a$ 的顺序，对答案的正确性无关，于是，我们对 $a$ 从小到大排一次序。

那么，我们就可以用二分查找出分界点 $x$ 的位置 $id$。所以，在 $id$ 之前的元素应在 $b$ 中；反之，应在 $c$ 中。

其实我们的答只于 $b,c$ 的和有关，与 $b,c$ 中真正有哪些元素无关。所以我们并不用求出 $b,c$。

因此，我们可以对排序过后的序列 $a$ 做一个前缀和，然后二分即可。

特别的，对于序列中没有 $x$ 的情况，答案应为 $|s_n - x \times n|$。

时间复杂度 $\Theta(q \log n)$

Code

#include <bits/stdc++.h>  
#define int long long  
#define re register  
  
using namespace std;  
  
const int N = 2e5 + 10;  
int n,q;  
int arr[N],s[N];  
  
inline int read(){  
    int r = 0,w = 1;  
    char c = getchar();  
    while (c < '0' || c > '9'){  
        if (c == '-') w = -1;  
        c = getchar();  
    }  
    while (c >= '0' && c <= '9'){  
        r = (r << 1) + (r << 3) + (c ^ 48);  
        c = getchar();  
    }  
    return r * w;  
}  
  
signed main(){  
    n = read();  
    q = read();  
    for (re int i = 1;i <= n;i++) arr[i] = read();  
    sort(arr + 1,arr + 1 + n);  
    for (re int i = 1;i <= n;i++) s[i] = s[i - 1] + arr[i];  
    while (q--){  
        int x;  
        x = read();  
        int id1 = lower_bound(arr + 1,arr + 1 + n,x) - arr - 1;//因为有可能有多个值为 x 的元素，所以求出值为 x 的区间的边界   
        int id2 = upper_bound(arr + 1,arr + 1 + n,x) - arr;  
        if (!id1 || id1 == n){//没查到  
            printf("%lld\n",abs(s[n] - n * x));  
            continue;  
        }  
        int pre = abs(id1 * x - s[id1]);//求答案   
        int nxt = abs((n - id2 + 1) * x - (s[n] - s[id2 - 1]));  
        printf("%lld\n",pre + nxt);  
    }  
    return 0;  
}