AtCoder Beginner Contest 342

比赛链接，官方题解

ID	Difficulty (0-5)	Topic	Status	Code
A	0	Brute Force	Solved	A.cpp
B	0	Brute Force	Solved	B.cpp
C	1	Implementation	Solved	C.cpp
D	1	Number Theory	Solved	D.cpp
E	2	Shortest Path	Solved	E.cpp
F	3	Probabilities	Solved	F.cpp
G	3	Segment Tree	Solved	G.cpp

F - Black Jack

两个人投一个 $D$ 面的骰子，每次投出来就把对应数字累计到自己的分数上。

对手的策略是一直投，直到总分 $y\ge L$ 。

• 如果最终你的总分 $x>N$ 你就输了；
• 否则如果对手的总分 $y>N$ 你会赢；
• 否则如果 $x>y$ 你才会赢，否则你输。

问你最优策略下赢的概率。

两人的得分是独立的。

对手的得分是 $x$ 的概率，以及得分 $>N$ 的概率可以用前缀和优化递推 $O(N)$ 算出。

自己这侧的 dp 倒着做，$g[x]$ 代表当前是 $x$ ，最优决策下最终的胜率是多少。

每次决策投还是不投即可，总复杂度 $O(n)$ 。

G - Retroactive Range Chmax

给定一个数列 $A$ ，支持如下三种操作：

• 类型 1：区间和输入的 $x$ 取 $\max$ ；
• 类型 2：撤销第 $i$ 个操作，保证第 $i$ 个操作是类型 1 且此前未被撤销过；
• 类型 3：在原数列上执行所有未被撤销的类型 1 操作后，查询 $A_i$ 的值。

线段树套 set + 标记永久化。

线段树每个节点 set<pair> 维护覆盖这个区间的类型 1 操作的 ($x$，操作编号）。

查询就是从根到叶子链上所有 set 里的 max 的 max 。

这样修改、撤销、查询复杂度都是 $(\log^2 n)$ 的了。总复杂度 $O(n\log^2 n)$ 。