偷一张图

By Sooke

定义 $f_u$ 为：$\mathrm{tag}_u = 1$ 的概率。

定义 $g_u$ 为：$u$ 的祖先存在 $\mathrm{tag} = 1$ 的概率。

1. 白色： $g=g/2,f=f/2$
2. 橙色： $f=(g+f)/2$
3. 深灰： $g=(1+g)/2,f=(1+f)/2$
4. 浅灰： $g=(1+g)/2$
5. 黄色：（啥都不用干

• 局面 $(x,y)~~~ x,y>0$
• 操作 $(x,y)\rightarrow(a,b)~~~a+b=x$ 或 $a+b=y$

$x,y\le 2\times 10^9$

先手必败还是必胜？

我们称一个排列是合法的，当且仅当每一个数都满足这个数比它相邻的数都要大或都要小。

求长度为 $N$ 的合法排列数量。

给定 $n\times m$ 整数矩阵，选取 $k\times k$ 正方形区域，使其中「最大值减最小值」最小

给定 $n\times m$ 棋盘，每格只能放 $1$ 个棋子，每行每列最多放 $2$ 个棋子，问方案数量

称贝壳的种类为颜色

考虑离线做法，将询问按照 $r$ 升序排序

发现只需要维护每个颜色的目前最右出现位置（ $\le r$ ）

每个颜色只在最后出现的地方进行统计，显然可以保证最优（因为离线）

举个例子

1
2
3
4
5
6
7
8
9
10
11
12
13

颜色序列为
1 3 1 2 1

扫到 1 （位置）
1 0 0 0 0
扫到 2
1 1 0 0 0
扫到 3
0 1 1 0 0
扫到 4
0 1 1 1 0
扫到 5
0 1 0 1 1

0/1 序列用树状数组维护即可，答案即是 0/1 序列 $sum(l, r)$

在线做法，用可持久化线段树即可

我写这一题是因为 BZOJ 的讨论

线段树（动态开点）裸题，讨论有点烦