原题链接

题意简述

有 $n$ 个同学站成一排($1 \leq n \leq 10^6$),一开始彼此不认识。每次给定一个区间 $[l,r]$,让区间内的同学都相互认识以下。求每次操作前区间内不认识的同学的对数。

思路

我们将 $n$ 个同学之间的认识状态用一个二维 0 / 1 矩阵,或者说一个 0 / 1 正方形表示出来。

一开始同学们相互都不认识,所以这个正方形内部除了对角线都是空的。现在我们操作区间 $[1,3]$,我在图形中使用红色标记这次操作。在操作之前,互相不认识的同学有 $3$ 对,也就是 $\dfrac{S_{empty}}{2}$。

现在给定区间 $[3,4]$,用黄色正方形覆盖这段区间。可以看到,在覆盖前只有一对同学互相不认识。

类似的,我们可以用蓝色标识区间 $[2,4]$。这之前的输出结果是 $1$。

如果我们继续操作区间 $[2,3]$,会发现它已经被填满了,答案为 $0$。

我们发现,每次加入的正方形,对角线都是共线的。也就是说,当横坐标确定,已填色区域的纵坐标是连续的,这对于使用数据结构维护很重要。那么我们就可以直接以横坐标为关键字,用线段树维护已填色区域的上边缘纵坐标。

加入正方形,相当于区间取最大值;已知已填色区域上边缘纵坐标之和,就可以求出每个合法正方形内的填色区域面积。

区间取最大值的时候,因为上边缘纵坐标是单调的,先二分找到需要更改的地方,然后区间覆盖。$\Theta(n\log n)$。

代码