这道题是线段树么（至少我是这么想的……但是写扯了）？

个人感觉类似吧

抽象一下问题就是上下两条线，每个抛物线抽象为一条线段（端点为两个端点），其实每次先插入一个抛物线在上面，如果和已有的有问题，就反过去（移到下面，如果还有冲突，这个不动，其他动），这样调整，如果调整不了了，那就不能达成，否则就一定可以达成。

由于不要求最优解，这样的算法一定是正确的。

关键问题就是如何快速地判断冲突和进行调整。

如果先把这些抛物线按abs(x2-x1)从大到小排序……这样再进行染色，新的抛物线先判断这两个端点的颜色是否一样，如果一样就不相交，然后进行染色……

不知是否有问题……

这样的确可以，我一开始就是这样写的

写到一半发现不对

因为染色的线段可能有重合的

比如抛物线 (1, 5) 和 抛物线 (2, 3) 不能算相交，但是它们重合

重合的话调整起来就麻烦了，而且怎么存储重合呢？

重合的话我觉得长的在下，短的在上……

不是，我的意思是说，重合的话按照题目的意思不是相交。

但是如果有几千个抛物线重合的话，假设在下面。然后新加入的抛物线和上面某几千个有冲突，要调整到下面，而它的顶点在下面那几千条抛物线的最里面，这样又和下面这几千条重合，这样你不论上/下总必须要移动几千条抛物线了吧。。。。这怎么处理呢

我想先处理线段长度大的（之前先排序），这样新的线段只可能在旧线段的内部（就是重合），然后染色时更新这一区域而不用考虑它之前的颜色。

这也不一定吧

比如抛物线都是：

(1, 100000)、(1, 99999)、(1, 99998)、。。。、（1, 3）

重合吧，你处理完了之后，再来个

(0, 2)

又完了

这样应该是相交吧……因为0的颜色是0（没颜色),2的颜色是(1,3)的颜色……

我明白你说的意思了……

是相交

假设因为某些原因（比如和其他抛物线有冲突），(0, 2) 这一段不能动，那么你所有的诸如 (1, 3)、(1, 4)、..、(1, 100000）这么多段都要移下去。。。。

这不久挂了。。。