随笔题解 Ct. 1
来源：Codeforces Round #816 (Div. 2)
为什么是 Ct 呢因为这是一整场比赛的题解。
为什么 tag 这么多呢因为一道题对应两三个 tag。
A. Crossmarket
有一个 $n\times m$ 的网格。Stanley 要从 $(1,1)$ 移动到 $(n,m)$，Megan 要从 $(n,1)$ 移动到 $(1,m)$。两个人可以在 $1$ 个单位时间内移动到自己当前所在格子四联通的格子，而且可以任意决定自己的出发时间。除此之外，Megan 会在经过的每个格子上留下传送门，Stanley 可以在 $1$ 个单位时间内在任意两个传送门之间移动。求两人到达各自终点的合计用时最少是多少。
多组数据。$1\leqslant n,m\leqslant 10^5$。
$\texttt{1s/256MB}$。
样例解释已经很明显地告诉了我们答案是 $2(n+m-2)-\max\{n-1,m-1\}$。
时间复杂度 $O(1)$，空间复杂度 $O(1)$。
B. Beautiful Array
构造一组 $a_1,a_2,\dots,a_n$ 使得
或判断无解。
多组数据。$1\leqslant n\leqslant 10^5$，$1\leqslant k\leqslant 10^9$，$0\leqslant b\leqslant 10^9$，$0\leqslant s\leqslant 10^{18}$。$\sum n\leqslant 10^5$。
$\texttt{1s/256MB}$。
显然有解当且仅当
构造也很简单。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。
C. Monoblock
给定序列 $a_1,a_2,\dots,a_n$。$m$ 次单点修改，每次修改后求
其中 $g(l,r)$ 表示 $a_l,a_{l+1},\dots,a_r$ 的极长连续段数量。
$1\leqslant n,m\leqslant 10^5$，$1\leqslant a_i\leqslant 10^9$。
$\texttt{1s/256MB}$。
可以将一次修改 $(x,v)$ 拆分为：删去包含位置 $x$ 的区间的贡献；将 $a_x$ 修改为 $v$；重新统计包含位置 $x$ 的区间的贡献。
甚至初始状态也可以拆分成 $n$ 次修改，第 $i$ 次为 $(i,a_i)$。
然后就……维护一下每个极长连续段的左右端点再写个线段树啥的数据结构查询一下就可以了。
懒得写了。
时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。
D. 2+ doors
设有一序列 $a_1,a_2,\dots,a_n$。有 $m$ 条限制，第 $i$ 条形如 $a_{u_i}\vee a_{v_i}=x_i$，其中 $\vee$ 表示按位或。
求一组字典序最大的解。输入数据保证至少存在一组解。
$1\leqslant n\leqslant 10^5$，$0\leqslant m\leqslant 2\times 10^5$，$1\leqslant u_i,v_i\leqslant n$，$0\leqslant x_i\lt 2^{30}$。
$\texttt{1.5s/256MB}$。
2-SAT。
时间复杂度 $O(n\log x_i)$，空间复杂度 $O(n+m)$。
E. Long Way Home
有一张 $n$ 个点 $m$ 条边的无向图，边有边权。每次可以沿着一条给定边移动，消耗的时间等于这条边的边权；也可以从点 $u$ 直接跳跃到点 $v$，消耗时间 $(u-v)^2$。
对于每个点 $i$，求在至多进行 $k$ 次跳跃的前提下，从点 $1$ 到点 $i$ 的最少用时。
$2\leqslant n\leqslant 10^5$，$1\leqslant m\leqslant 10^5$，$1\leqslant k\leqslant 20$，无重边，可能有自环，$1\leqslant$ 边权 $\leqslant 10^9$。
$\texttt{3s/256MB}$。
令 $f(u,i)$ 表示至多进行 $i$ 次跳跃，到达点 $u$ 的最少用时。那么显然 $f(u,0)$ 可以一遍 Dijkstra 求出。
设当前已经求出了 $f(u,i)$。令 $g(u,i)$ 表示表示至多进行 $i$ 次跳跃，且最有一次移动恰好是一次跳跃，到达点 $u$ 的最少用时。有
这部分可以一遍斜率优化 DP 求出。
在这之后，建立一个超级源点 $0$，向其他每个点连一条边权为 $0$ 的边。令点 $u$ 此时的 dist 为 $g(u,i+1)$，用 Dijkstra 更新一遍从点 $0$ 出发的最短路，此时点 $u$ 最终求得的最短路长度就是 $f(u,i+1)$ 的值。
时间复杂度 $O(k(m\log n+n))$，空间复杂度 $O(n+m)$。
F. Crop Squares
这是一道交互题。
在平面直角坐标系中有一个矩形，四个顶点分别为 $(0,0)$，$(0,m)$，$(n,0)$ 和 $(n,m)$。其中有一个平行于坐标轴的 $1\times 1$ 的正方形被标记了。这个正方形被矩形完全包含。
每次询问，您可以给出一个面积严格为正的简单多边形，交互库会返回这个多边形与被标记正方形的并的面积。这个多边形不需要被矩形完全包含。
您需要在至多 $5$ 次询问内给出被标记正方形的左下角坐标。
$1\leqslant n,m\leqslant 100$。
$\texttt{1s/256MB}$。
神仙题。
只需要两次询问。
第一次询问给出一个下图中的蓝色多边形：
其中红色区域是要求的被标记正方形，绿色区域是二者的并。
若被标记正方形左下角坐标为 $(x,y)$，绿色区域面积为 $S$，有
可以解得
第二次询问给出一个下图中的蓝色多边形：
令绿色区域面积为 $T$，同理有
时间复杂度 $O(n+m)$，空间复杂度 $O(1)$。