E：先钦定所有都是1，然后需要变成0，每一次选择尽量多的1变为0，不够的用0来补充，贪心下去即可。或者DP，设
f
i
f_i
fi表示
i
i
i个
1
1
1要操作多少次得到，可以将
f
j
,
f
k
f_j,f_k
fj,fk转移到
f
j
+
k
−
2
i
f_{j+k-2i}
fj+k−2i，然后倒着模拟回去即可。
F
主要需要简化模型之后发现性质。
显然建图之后tarjan缩点，然后需要在DAG上选点，使得所有下往上第
a
i
a_i
ai个关键点都能够被覆盖。
首先将切比雪夫距离转化为曼哈顿距离，原图中的点
(
x
,
y
)
(x,y)
(x,y)在新图中的
(
x
+
y
,
x
−
y
)
(x+y,x-y)
(x+y,x−y)上，那么原图中的移动变为了
(
+
1
,
+
1
)
(+1,+1)
(+1,+1)或
(
+
1
,
−
1
)
(+1,-1)
(+1,−1)，因此当
x
=
X
x=X
x=X时曼哈顿距离最小。
现在我们需要优化一个简单的DP，
f
x
,
y
f_{x,y}
fx,y表示在
(
x
,
y
)
(x,y)
(x,y)的最小答案，显然固定一个
x
x
x，
f
x
,
y
f_{x,y}
fx,y是关于
y
y
y的分段函数，进一步的这是一个凸函数（由于若干个凸函数加起来还是一个凸函数），并且斜率的总变化不超过
n
n
n。
现在我们需要维护两个操作：1.将原函数向两边扩充，2.将当前函数加上一个
V
V
V型的函数。
考虑1操作只需要将最小值的区间扩大，两边顶点同时扩，因此我们可以对于极值左边和右边分别维护一个单调队列，单调队列可重复并且每一个点按顺序表示斜率1的变化，又有所有的端点根据
x
x
x加或减，因此不妨将
x
x
x当作全局tag，存
y
−
x
y-x
y−x至堆中。
考虑2操作，相当于是在
V
V
V的顶点插入两个点，表示斜率
+
2
+2
+2的变化，需要同时维护答案以及两个堆堆顶的变化，即有一个堆顶移到了另一边。