解释我自己初学这道题目遇到的许多细节和疑问,是我自己想出来的,因为是自学的,所以有可能有错误,如果发现错误,请在评论区告诉我,非常感谢!
在简化问题考虑左下中,为什么按照横坐标从小到大排序就好了?不应该还要以纵坐标为第二关键字排序吗?不然有可能某次询问$(x,y)$的下面一个点$(x_i,y_i)$($(y_i<y)$)还没有更新就轮到$(x,y)$了,这就无法统计了啊?
答:如果单独考虑左下的话,这个做法确实有问题,也的确需要以纵坐标为第二关键字排序。但是如果考虑四个方向的话,只以横坐标排序就是没问题的,上面说的这种情况会在其他时候被统计到。比如就说上面说的这种情况,那么当这种情况出现的时候,我们左下的确是无法统计$(x,y)$的,但是轮到统计右下的时候,我们此时(相对于左下)是倒着循环的,之前在左下没有被先添加进去的$(x_i,y_i)$说明他在序列中的位置在$(x,y)$之后,所以此时就一定会被先添加,然后就会被统计了
为什么可以用树状数组统计没有可加性的最大值?
答:我们考虑一下为什么树状数组不能统计最大值。翻到蓝书的P203,看看那个树状数组的图,想一下如果我们没有修改操作而是只有初始的序列,那么我们如何更新树状数组?答案当然就是对每一个树状数组,对他的所有儿子取最大值(比如$c[16]=max(c[8],c[12],c[14],c[15],a[16])$),没有修改操作的情况下,这个显然是对的($c[i]$维护的就是$[i-lowbit(i)+1,i]$的最大值)。那我们现在加入修改操作。如果我们将$a[i]$修改为$k$,用最暴力的方法,如果更新$c$数组?这里不太好用文字说明,我先举一个例子。比如修改$a[12]$,那我们先找到$c[12]$,令$c[12]=max(c[10],c[11],k)$,然后再找到$c[16]$,令$c[16]=max(c[8],c[12],c[14],c[15],a[16])$。所以就是找到对应位置的树状数组,然后一路往上,对经过的每一个节点,都要重新对其所有儿子取最大值。之所以要这么做,是因为有可能会出现一种情况,比如$c[12]$刚好等于$a[12]$,而$a[12]$恰好又是$[9,12]$的严格最大值,而我们修改的$k$刚好严格小于$a[12]$,这下就没办法直接说明$c[12]$最新的最小值了,所以我们必须比较暴力的更新。然而对于一般的问题来说,即使我们暴力更新了,我们也没办法查询$[l,r]$的最大值,因为最大值是没有可加性的。但是回到这一道题目,可以证明,四个方向都不会出现上述说明的情况,比如统计左下方的时候,扫描到一个点$(x_i,y_i)$,由于我们按照了$x$从小到大排序,此时修改序列的$a[y_i]$,一定能被修改成功(也就是上文说的$k$一定大于$a[y_i]$),于是就不会出现上文说的情况,所以就可以像代码一样区间更新。而这道题目刚好又是只用查询$[0,y]$的最大值,所以即使不满足可加性问题也不大
为什么统计左上的时候修改的位置要变为$10^6-y_i$?
答:就像上文提到的,这里之所以能用树状数组是因为我们不用满足可加性,查询的是$[0,y]$,这里为了继续利用这个性质,由于我们此时要查询的是$[y,10^6]$,所以我们要把他倒过来统计
最后提一嘴时间复杂度的计算,一共有$log(N+M)$层,每层的总时间复杂度$(N+M)log(N+M)$,所以时间复杂度为$O((N+M)log^2(N+M))$
最大值具有可加性,但是不可差分