T1 廊桥分配

题意：给两组线段，分别m1m1m1 、m2m2m2 个，共计nnn 条直线，要求每组内线段起点靠前的必须优先放置，同一条直线上的线段互不相交，问如何分配这nnn 条直线使线段放置的总数最多

首先OOO(n 2 lognn^2lognn2logn)的做法很显然，枚举分配给xxx 组1−n1-n1−n 个廊桥，yyy 组相应的用nnn 减，然后模拟飞机进廊桥算总和取maxmaxmax 即可

考虑怎么优化

挖掘题目性质：根据“先到先得”的原则，只要来了一个飞机，只要还有空余的廊桥，就必须把它放进去，所以当这一组廊桥数目增多时，原来在哪个廊桥的飞机仍然在哪个廊桥。

（重点部分：）所以，如果强制让它进入编号最小的廊桥，这样不会影响进入廊桥飞机的集合。这样的话，我们在每个编号为iii 的廊桥上记录可以放多少个飞机ccc[iii] ，那么给该组aaa 个廊桥时，放的飞机总数就是ccc[111] 到ccc[aaa] 的和，即前缀和。这样预处理，我们成功将外层枚举分配廊桥个数的复杂度降下来了。现在复杂度为OOO(nlognnlognnlogn)

最后说一下用小根堆来模拟飞机进廊桥的过程，开一个堆sss ，表示现在可用的廊桥编号，堆qqq 表示在廊桥内的飞机的结束时间和其所在的廊桥编号（用个pairpairpair 打包即可）。具体实现：我们钦定来一个飞机先进入编号小的廊桥，对于一个新来的飞机xxx ，先把所有已占廊桥中的飞机的结束时刻比xxx 到达时刻小的poppoppop 掉，然后若还有剩余廊桥，就把xxx 的结束时刻捆上当前空余廊桥的最小编号扔进堆里。