D

交互题
平面内有两个不相交的矩形
每次询问一个矩形区域,返回区域内有多少个矩形(完全覆盖)

交互题就二分。。。

先二分出第一个矩形,可以从做向右二分出x2,然后从x2向左二分出x1
y坐标同理
用同样的方法二分第二个矩形时把第一个矩形去掉

E

给定一个序列A,问最少的改变量,使得其成为严格单调递增序列

DP

令$B_i = A_i = A_i - i$ (保证严格递增)
然后对 $B$ 排序
现在将$A$以最小代价变成一个非严格递增序列$A’$
可以确定$A’$中每个元素与$B$中对应
然后做一个$O(n^2)$的DP即可
$d(i,j)$ 表示前i个元素非严格递增,匹配到第$B_j$的最小答案

证明:
如果序列中存在一个不是$B$中的数,那么我们总能将这个数+1或-1
使得序列还保持非严格单增,而总代价会减少