Moscow Pre-Finals Workshop 2016. Japanese School OI Team Selection.

Problem A

Solvde by Kilo_5723. 0:43 (+)

Problem B

Unsolved.

Problem C

Solved by Xiejiadong. 1:29 (+1)

题意：要求支持两个操作：

• 查询所有高度 $\ge x$ 的连续的有几段；
• 修改某一个高度。

题解：考虑修改一个高度的时候，根据旁边两个的高度分情况讨论可能出现的联通块改变。

用树状数组维护所有高度 $\ge x$ 的联通块数量。

Problem D

Solved by Weaver_zhu. 3:55 (+2)

Problem E

Solved by Weaver_zhu. 2:38 (+)

Problem F

Unsolved.

Problem G

Solved by Weaver_zhu. 1:18 (+)

Problem H

Solved by Xiejiadong. 2:06 (+1)

题意：每次选择一个方向走到底（直到遇到冰块），每次出发的位置会变成冰块，求从起点到终点至少走多少路。

题解：考虑有两种走法：

• 从当前位置开始，选择一个方向走到底，代价为 $1$ ；

• 从当前位置走到相邻位置，代价为 $2$ （选择一个方向走到底再回来）。

建图以后跑最短路即可。

Problem I

Solved by Weaver_zhu. 2:48 (+2)