Solution. CF1817E Half-sum

Description

给定一个大小为 $n$ 的 multiset $\{a_1,a_2,\dots,a_n\}$，每次取出两个数 $x,y$ 将其删去然后插入 $\dfrac{x+y}{2}$，最终剩下两个数 $A,B$，试最大化 $|A-B|$。

$2\le n\le 10^6,0\le a\le 10^9$

Solution

不妨设 $A\le B$。如果我们将所有数从小到大排序，显然最终 $A$ 由一段前缀合成，而 $B$ 由剩下的后缀合成。

每次将两个数替换为它们平均数的操作可以表示为一个二叉树结构，我们希望最后得到的数尽量小 / 尽量大，于是可以通过调整法证明这棵树的任意一个非叶子结点都至少有一个儿子是叶子。换言之，所有数最终的贡献系数一定是 $2^{-1},2^{-2},\dots,2^{-k},2^{-k}$ 这样的形式，根据排序不等式或显然法，分配给前缀的系数一定从大到小，分配给后缀的系数一定从小到大。

这样，如果前缀与后缀的划分位置已知，我们就已经能够计算答案了。

我们将划分点定义为前缀的结尾处，注意到，如果划分点在 $[l,r)$ 中变化，$[1,l-1]$ 与 $[r + 1,n]$ 的贡献系数都是固定的，这使得我们可以进行分治，在一个分治区间中，我们只需要计算区间内的数对答案的贡献即可。注意 $r$ 这个点较为特殊，在程序中要注意实现细节。

找最优划分点一定需要比较大小，所以我们不能直接取模，必须维护高精二进制数，其应当支持单点加减，判断符号。为了方便实现，我们会将所有贡献系数统一乘上 $2^n$。

通过「允许某一位上的值为负数¹²」，单点加减可以做到均摊线性（压位），而判断符号则可以直接找到最高的有值的位判断其正负，注意找最高的有值的位不能用 map，否则多只 $\log$，由于有线性的进位均摊并且判断符号只会做一次，我们直接暴力检查一遍所有修改过的位即可。

总复杂度可以认为是 $O(n\log n)$。

Code

namespace Main{
    const int N = 1000005;
    const int MOD = 1e9 + 7;
    int t, n, a[N];
    struct bin{
        static const int base = 1 << 30;
        vector<ll> a, vis;
        bin() { a.resize(N); }
        void reset(){
            for(int x: vis) a[x] = 0;
            vis.clear();
        }
        // add x * 2 ^ k
        void add(ll x, int k){
            x = x * (1 << (k % 30)), k /= 30;
            a[k] += x;
            vis.push_back(k);
            while(abs(a[k]) >= base){
                a[k + 1] += a[k] / base;
                a[k] %= base;
                vis.push_back(k + 1);
                k++;
            }
        }
        int sgn(){
            int pos = -1;
            for(int x: vis) if(a[x] != 0) pos = max(pos, x);
            if(pos == -1) return 0;
            else if(a[pos] > 0) return 1;
            else return -1;
        }
    }tmp;
    void calc(bin &res, int l, int r, int k, int coef){
        for(int i = l; i < k; i++) res.add(-coef * a[i], n - i);
        for(int i = k + 2; i <= r; i++) res.add(coef * a[i], i - 1);
        res.add(-coef * a[k], n - k + 1);
        if(k < r) res.add(coef * a[k + 1], k + 1);
    }
    int solve(int l, int r){
        if(l == r) return l;
        int mid = l + r >> 1;
        int p1 = solve(l, mid), p2 = solve(mid + 1, r);
        tmp.reset();
        if(p2 < r){
            calc(tmp, l, r, p1, 1), calc(tmp, l, r, p2, -1);
            p1 = tmp.sgn() >= 0 ? p1 : p2, p2 = mid;
            tmp.reset();
        }
        else p2 = mid;
        calc(tmp, l, r, p1, 1), calc(tmp, l, r, p2, -1);
        return tmp.sgn() >= 0 ? p1 : p2;
    }
    ll qpow(ll n, ll k){
        ll res = 1;
        while(k > 0){
            if(k & 1) res = res * n % MOD;
            n = n * n % MOD;
            k >>= 1;
        }
        return res;
    }
    void Main(){
        input(t);
        while(t--){
            input(n);
            for(int i = 1; i <= n; i++) input(a[i]);
            sort(a + 1, a + n + 1);
            int p = solve(1, n);
            tmp.reset();
            calc(tmp, 1, n, p, 1);
            ll num = 0;
            sort(tmp.vis.begin(), tmp.vis.end());
            tmp.vis.erase(unique(tmp.vis.begin(), tmp.vis.end()), tmp.vis.end());
            for(int x: tmp.vis) num = (num + tmp.a[x] * qpow(2, x * 30) % MOD + MOD) % MOD;
            num = num * qpow(qpow(2, n), MOD - 2) % MOD;
            write(num);
            puts("");
        }
        return;
    }
} // namespace

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。