Educational Codeforces Round 187 (Rated for Div. 2)-CF-Edu-187-E. Probabilistic Card Game

题目大意

https://codeforces.com/contest/2203/problem/E

题目描述

Alice 和 Bob 有一个初始为空的牌堆。游戏共进行 $m$ 回合，在第 $i$ 回合中，会发生以下事件：

1. 一张数值为 $a_i$ 的牌被加入牌堆（保证加入的牌数值各不相同）。

2. 如果牌堆中的牌数少于 $3$ 张，该回合直接结束。

3. 否则，Alice 从牌堆中选择一张牌，设其数值为 $a$。

4. 接着，Bob 在知道 Alice 选了哪张牌的情况下，从剩下的牌中选择一张牌，设其数值为 $b$（$b \neq a$）。

5. 最后，从剩下的 $i-2$ 张牌中等概率随机抽取一张牌，设其数值为 $c$。

6. 回合结束后，这三张牌被放回牌堆。

得分规则

在确定了 $a, b, c$ 的值后，Bob 的得分按以下规则计算：

• 如果 $|a - c| \le |b - c|$，Bob 得 $0$ 分；

• 如果 $c$ 的值严格介于 $a$ 和 $b$ 之间（即 $a < c < b$ 或 $b < c < a$），Bob 得 $0$ 分；

• 其他情况下，Bob 得分为 $|b - c|$。

游戏目标

在每回合中，Alice 的目标是最小化 Bob 的期望得分，而 Bob 的目标是最大化他的期望得分。两人均采取最优策略。（注意：两人是根据真实期望得分来做最小化或最大化的决策，而非取模后的值）。

输入格式

第一行包含一个整数 $m$（$3 \le m \le 2 \cdot 10^5$），表示回合数。
第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$（$1 \le a_i \le 10^{12}$，所有 $a_i$ 互不相同），表示每回合加入牌堆的牌的数值。

输出格式

输出 $m-2$ 个整数，第 $i$ 个数表示在第 $i+2$ 回合中，双方在最优策略下 Bob 的期望得分对 $998244353$ 取模后的结果。

样例 1

Input:
5
1 10 3 11 7

Output:
0
499122177
665496236

样例 1 解释

这三个输出分别对应第 $3, 4, 5$ 回合。真实的期望得分依次为 $0, \frac{1}{2}, \frac{2}{3}$。

样例 2

Input:
6
23 7 11 24 10 28

Output:
0
499122177
1
748683266

样例 2 解释

这四个输出分别对应第 $3, 4, 5, 6$ 回合。真实的期望得分依次为 $0, \frac{1}{2}, 1, \frac{5}{4}$。

样例 3

Input:
9
4 10 7 1 16 5 9 12 2

Output:
0
499122178
2
499122178
798595484
831870296
427819010

样例 3 解释

真实的期望得分依次为 $0, \frac{3}{2}, 2, \frac{3}{2}, \frac{8}{5}, \frac{11}{6}, \frac{11}{7}$。

思路讲解

通过模拟，我们发现，首先，选了 A 的位置以后，B 其实只有两种选择，B 必须紧紧挨着 A 选。

然后，我们就是要确定这个 A 的选择。我们可以采用一种二分两次的方法（我自己瞎想的）。或者你也可以三分。

图中的 res 就是使用树状数组查询的蓝色部分的这个查询结果。

核心的这个做法这个 lambda 是这个东西，他能够在知道目前长度的情况下，求解出这个答案。

    auto find_ans = [&](ll len) -> ll {
        ll l = 0, r = len - 1;
        auto cal_left = [&](ll ia) -> ll {
            ll pa = processing_pos[ia];
            if (ia <= 2) {
                return 0;
            }
            ll res = tr.query(1, processing_pos[ia - 2]);
            ll pb = processing_pos[ia - 1];
            res = li_pos_to[pb].val * (ia - 2) - res;
            return res;
        };
        auto cal_right = [&](ll ia) -> ll {
            if (ia >= len - 1) {
                return 0;
            }
            ll pa = processing_pos[ia];
            ll pb = processing_pos[ia + 1];
            ll res = tr.query(processing_pos[ia + 2], N);
            res = res - li_pos_to[pb].val * (len - ia - 1);
            return res;
        };
        auto check1 = [&](ll p) -> bool {
            // 这个程序，只要左边比右边大，就 return false
            return cal_left(p) >= cal_right(p);
        };
        auto check2 = [&](ll p) -> bool {
            // 这个程序，只要左边比右边大，就 return false
            return cal_left(p) <= cal_right(p);
        };
        while (l < r) {
            ll mid = l + r >> 1;
            if (check1(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        ll ans1 = l;
        l = 1, r = len;
        while (l < r) {
            ll mid = l + r +1 >> 1;
            if (check2(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        ll ans2=l;
// #ifdef LOCAL
//         debug(ans1);
//         debug(ans2);
//         debug(cal_left(ans1));
//         debug(cal_right(ans2));
// #endif
        ll res=min(max(cal_left(ans1),cal_right(ans1)),max(cal_right(ans2),cal_left(ans2)));
        res%=mod;
        res*=binpow(len-2,mod-2);
        res%=mod;
        return res;
    };

AC代码

AC

https://codeforces.com/contest/2203/submission/364812724

源代码

/**
 * Problem: E. Probabilistic Card Game
 * Contest: Educational Codeforces Round 187 (Rated for Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2203/problem/E
 * Created: 2026-02-26 01:59:35
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT, testcase;

/*
 *
 */


// by znzryb
// 普通的单点修改区间查询树状数组，含有查找第K个空位，第K个元素的功能
// https://www.codechef.com/viewsolution/1179893708 查找第K个元素测试
// 第K个空位的测试应该是一道abc的题目，但是当时没保存
struct BIT {
    vector<ll> tr;
    int n;

    inline int lowbit(int x) {
        return x & (-x);
    }

    BIT(int ln) {
        // 构造+初始化函数
        n = ln;
        tr.resize(n + 5, 0);
    }

    BIT() {
    }

    inline void add(int p, ll x) {
        if (p == 0) return;
        while (p <= n) {
            tr[p] += x;
            p += lowbit(p);
        }
    }

    inline ll query(int l, int r) {
        ll lres = 0, rres = 0;
        l -= 1;
        while (l > 0) {
            lres += tr[l];
            l -= lowbit(l);
        }
        while (r > 0) {
            rres += tr[r];
            r -= lowbit(r);
        }
        return rres - lres;
    }

    inline int findkth(int k) {
        // 找到第k个元素，当然应当是要求只能出现0和1
        int x = 0, sum = 0;
        for (int i = __lg(n); ~i; --i) {
            x += 1 << i;
            if (x >= n || sum + tr[x] >= k) {
                x -= 1 << i;
            } else {
                sum += tr[x];
            }
        }
        return x + 1; // 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新元素出现的地方
    }

    inline int kthspace(int k) {
        // 找到第k个空位，当然应当是要求只能出现0和1
        int cx = 0;
        for (int i = 1 << 20; i > 0; i >>= 1) {
            // 这个你可以理解为不断缩小步长的搜索
            if (cx + i <= n && lowbit(cx + i) - tr[cx + i] < k) {
                // lowbit(cx)-tr[cx+i] 表示cx+i这个树状数组区间有多少空位
                k -= lowbit(cx + i) - tr[cx + i];
                cx += i;
            }
        }
        return cx + 1; // 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新空位出现的地方
    }
};


struct Val_id {
    ll val, id;

    bool operator<(const Val_id &o) const {
        if (val != o.val) {
            return val < o.val;
        }
        return id < o.id;
    }
};

// 在 k<=0 的时候返回 1
ll binpow(ll a, ll k, const ll &p = mod) {
    ll res = 1;
    a %= p;
    while (k > 0) {
        if ((k & 1) == 1) res = a * res % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

void Solve() {
    ll N;
    cin >> N;
    vector<Val_id> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i].val;
        A[i].id = i + 1;
    }
    vector<Val_id> li_pos_to = A;
    A.insert(A.begin(),Val_id{});
    sort(all(li_pos_to));
    li_pos_to.insert(li_pos_to.begin(), Val_id{});
    vector<ll> id_to_pos(N + 2);
    for (int i = 1; i <= N; ++i) {
        // 树状数组不能处理 0-based
        id_to_pos[li_pos_to[i].id] = i;
    }
    BIT tr(N);
    vector<ll> processing_pos = {0};
    auto find_ans = [&](ll len) -> ll {
        ll l = 0, r = len - 1;
        auto cal_left = [&](ll ia) -> ll {
            ll pa = processing_pos[ia];
            if (ia <= 2) {
                return 0;
            }
            ll res = tr.query(1, processing_pos[ia - 2]);
            ll pb = processing_pos[ia - 1];
            res = li_pos_to[pb].val * (ia - 2) - res;
            return res;
        };
        auto cal_right = [&](ll ia) -> ll {
            if (ia >= len - 1) {
                return 0;
            }
            ll pa = processing_pos[ia];
            ll pb = processing_pos[ia + 1];
            ll res = tr.query(processing_pos[ia + 2], N);
            res = res - li_pos_to[pb].val * (len - ia - 1);
            return res;
        };
        auto check1 = [&](ll p) -> bool {
            // 这个程序，只要左边比右边大，就 return false
            return cal_left(p) >= cal_right(p);
        };
        auto check2 = [&](ll p) -> bool {
            // 这个程序，只要左边比右边大，就 return false
            return cal_left(p) <= cal_right(p);
        };
        while (l < r) {
            ll mid = l + r >> 1;
            if (check1(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        ll ans1 = l;
        l = 1, r = len;
        while (l < r) {
            ll mid = l + r +1 >> 1;
            if (check2(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        ll ans2=l;
// #ifdef LOCAL
//         debug(ans1);
//         debug(ans2);
//         debug(cal_left(ans1));
//         debug(cal_right(ans2));
// #endif
        ll res=min(max(cal_left(ans1),cal_right(ans1)),max(cal_right(ans2),cal_left(ans2)));
        res%=mod;
        res*=binpow(len-2,mod-2);
        res%=mod;
        return res;
    };
    for (int i = 1; i <= N; ++i) {
        tr.add(id_to_pos[i], A[i].val);
        // processing_pos.push_back(id_to_pos[i]);
        processing_pos.insert(lower_bound(all(processing_pos), id_to_pos[i]),
                              id_to_pos[i]);
        if (i <= 2) {
            continue;
        }
        ll res=find_ans(i);
        cout<<res<<"\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
    Solve();
    return 0;
}

/*

*/

心路历程（WA，TLE，MLE……）

虽然是权值线段树（树状数组），但是还是加的这个值。

不要搞反顺序了。