起因

codeforces 1408 D

做这道题时没有什么思路,于是看了官方题解,但是看不懂,于是看了另一篇题解终于明白了意思,由于N 和 M都是2e3 级别的所以求出每一对之间的边界值,之后从右向左染色.

理解

这和我第一次看见差分的代码时的感觉非常相似.前面的操作中只进行O(1)的两次点修改,最后询问时,进行一次O(n)的统一染色.将前面需要进行的区间修改加在最后一次完成. 这个题中也满足对于所有的小于等于c[j]-a[i]的x都需要大于d[j]-b[i]+1,我们先在需要染色区间的最右端染色.在最后询问时,进行从右向左的区间染色.由于在右端点上的覆盖会发生在整个区间上.则这种覆盖是合法的.