考场的时候用单调队列写了O(n2logn)的做法,这里给出一种严格O(nlogn)做法,代码略去。
对于两种飞机分开考虑,记cnt1/2[n]表示两种飞机在第n条廊道分别停几架,显然由于入队顺序一定,不管有多少条廊道这些飞机都会停到同一个廊道上,对每个区间排序后依题意模拟,建立一棵权值线段树维护廊道号,插入一架飞机查询小于当前区间起始点区间中的廊道号最小值,如有,则删去上一架此廊道号的飞机结束点处的值,修改结束点为当前廊道号。如没有满足条件的廊道则说明需要停到一个新的廊道,取新的廊道号修改结束点为当前廊道号。考虑到区间点值范围为[1,100000000]显然会爆空间,可以使用离散化或动态开点线段树优化。
我确实不太懂set怎么维护这个东西。