Educational Codeforces Round 187 (Rated for Div. 2)-CF-Edu-187-E. Probabilistic Card Game · znzryb
## 题目大意
[https://codeforces.com/contest/2203/problem/E](https://codeforces.com/contest/2203/problem/E)
**题目描述**
Alice 和 Bob 有一个初始为空的牌堆。游戏共进行 $m$ 回合，在第 $i$ 回合中，会发生以下事件：
1. 一张数值为 $a_i$ 的牌被加入牌堆（保证加入的牌数值各不相同）。
1. 如果牌堆中的牌数少于 $3$ 张，该回合直接结束。
1. 否则，Alice 从牌堆中选择一张牌，设其数值为 $a$。
1. 接着，Bob 在知道 Alice 选了哪张牌的情况下，从剩下的牌中选择一张牌，设其数值为 $b$（$b \neq a$）。
1. 最后，从剩下的 $i-2$ 张牌中等概率随机抽取一张牌，设其数值为 $c$。
1. 回合结束后，这三张牌被放回牌堆。
**得分规则**
在确定了 $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 是这个东西，他能够在知道目前长度的情况下，求解出这个答案。
```cpp
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](https://codeforces.com/contest/2203/submission/364812724)
::: 源代码
```cpp
/**
* 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……）
虽然是权值线段树（树状数组），但是还是加的这个值。
不要搞反顺序了。
