我带错题了吗。为什么我一个早读想出来 EFG 还有一堆人说难的。
E
定义数组 BBB 满足 Bi=∣Ai−Ai−1∣B_i=|A_i-A_{i-1}|Bi =∣Ai −Ai−1 ∣，则答案为 minj=lrBj≥k\min_{j=l}^r B_j\ge kminj=lr Bj ≥k 的 l,rl,rl,r 数量。
显然可以 set O(nlogn)O(n\log n)O(nlogn) 求出。
F
未来十年无人看懂出题人设计意图。
考虑树形 DP。令 dp[i][j]dp[i][j]dp[i][j] 表示是否可以通过 3k+j3k+j3k+j 次操作将 iii 的子树删完。显然是个背包问题，可以 O(nk2)O(nk^2)O(nk2) 解决，答案就是 dp[1][0]dp[1][0]dp[1][0]。
优化 1:压位，可以做到 O(nk)O(nk)O(nk)。
优化 2:在压位的基础上预处理所有更新情况，做到 O(k22k+n)O(k2^{2k}+n)O(k22k+n)。
G
何意味。这是 div3 最后一题？出题人我真求你了。
注意到 ddd 单调递增，minAi\min A_iminAi 单调不增，所以 d−minAid-\min{A_i}d−minAi 单调递减，可以线段树二分得出是否存在。显然如果存在答案一定为 111。
O(n+qlogn)O(n+q\log n)O(n+qlogn)。
