$O(N + Q\log{N})$ ができた。本番中に解き切りたかった

問題概要

$N$ 個の整数 $A_1, A_2, \dots, A_N$ がある。整数 $x$ を 1 つ固定したとき、先手と後手は以下のようにしてゲームを進める:

先手は現在残っている整数のうち、最大のものを取って足す
後手は現在残っている整数のうち、 $x$ に最も近いものを取って足す (最も近いものが複数あるならばそのうち小さい方)

このときの先手が獲得するポイントの合計値を求めたい。クエリとして $x$ が $Q$ 種類指定される。

制約

$2 \le N \le 10^{5}$
$1 \le Q \le 10^{5}$

考えたこと

いくつかの $x$ について具体的に手を動かしていくうちに

高橋君の合計ポイントとしてありうるものは高々 $O(N)$ 通りしかないのでは

という気持ちになって来た。それを決定付けるために、ゲームがどんな風に進行するのかを一般的に考えてみる。

そうすると、ゲームの途中までは上図のように、

先手は右端から順に
後手は $x$ 付近から左右に

伸ばしていくことになる。ここで後手については $x$ の左右から何個ずつとっていくかはわからないが、ともかく「連続した区間からとっていく」ことにはかわりない。

その状況が変わるのが、「先手の次にとりたいやつが後手にもうとられている」という状態になったとき。具体的には上図のように、先手のとった領域と後手のとった領域とが接するようになったとき。そこから先は下図のように、先手と後手が交互にとっていく感じになる。

よって、上記の予想はただしくて

「先手と後手がそれぞれ前半の間に広げる領域の広さ」が $1, 2, \dots, N/2$ の場合

の $N/2$ 通りの場合があることになる。ただし $N$ が奇数のときはこれに加え、「先手と後手がともに両端からとっていって、最後に先手が真ん中をとる」という場合もある。

僕は、これらの場合の境目となる $x$ の値をあらかじめすべて求めておくことにした。そして各クエリに対して、upper_bound を用いることで、どの場合に属するのかを高速に判定することができる。境目となる $x$ は、上図の後手の青い広い領域の左端 (左開区間) と右端 (右閉区間) との中央にある。すなわち数列の index を右から数えることにすると

先手の赤領域は $0, 1, ..., i$ としたとき
後手の青領域は $i+1, i+2, ..., 2i+1$
境目となる $x$ は (A[ $i+1$ ] + A[ $2i+2$ ])/ $2$ $+ 1$

残ったタスクは $i$ の値がわかっていたときに先手の合計値を求める作業だが、これは

A の累積和
A の右から偶数番目だけとる累積和

を管理していれば高速に求めることができる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, Q; cin >> N >> Q;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    reverse(A.begin(), A.end()); // 考えやすいように左右反転
        
    vector<long long> sum(N+1), evensum(N+1); // 累積和、偶数番目累積和
    for (int i = 0; i < N; ++i) {
        sum[i+1] = sum[i] + A[i];
        evensum[i+1] = evensum[i] + (i % 2 == 0 ? A[i] : 0);
    }
        
    vector<long long> ths, vals; // ths: L の値が変化する x の境目、vals: またそのときの先手のスコア
    for (int i = 0; i < (N-1)/2; ++i) {
        long long th = (A[i+1] + A[i*2+2])/2 + 1;
        long long val = (sum[i+1] - sum[0]) + (evensum[N] - evensum[i*2+2]);
        ths.push_back(th); vals.push_back(val);
    }
    reverse(ths.begin(), ths.end()); reverse(vals.begin(), vals.end());
    for (int _ = 0; _ < Q; ++_) {
        long long x; cin >> x;
        int it = upper_bound(ths.begin(), ths.end(), x) - ths.begin(); // L の値が何かを求める
        if (it == 0) cout << sum[(N+1)/2] - sum[0] << endl;
        else cout << vals[it-1] << endl;
    }
}