【题解】西北大学集训队选拔赛（重现赛）

A 坐飞机

按第i航班降落时间和第i+1航班起飞时间的差值排序，贪心即可。

B 饱和式救援

对于同一个发电机救援成功的概率= 1 –不成功的概率

然后考虑动态规划DP i j代表第i个发动机，已经救援j个发动机的概率，递推即可.

C 晾衣服

排序之后贪心，或者直接二分答案进行check都可以。

D 温暖的签到题

区间修改和查询，考虑线段树维护。

将l~r改为1~r-l+1，发现修改后的值递增1，而被修改的元素下标也递增1。那么就可以在线段树中不用真的修改成1~r-l+1，而是全部修改成l-1，然后区间查询的时候用元素下标之和（等差数列或者前缀和预处理）减去线段树中的值。

初始线段树中元素均为0.

注意爆int的情况。

E 西湖奇遇记Ⅰ

最短路径考虑dij

由于可以用多次加速，那么在最短路的过程中加入一个k表示用了几次加速即可。（建立多层图）

（数据里的边数是2e5，有人RE了应该是这个锅，题面录的时候不仔细，sorry）

F 三生三世

先判断是否完全一样。

然后直接排序后比较，或者统计字符出现次数。

G 序列操作

双指针，贪心的修改后面的值，尽量修改成-M，直到区间和为负数（那本次操作就不修改到-M了）。

或者树状数组维护单点修改+区间查询也可。

H 偶数计算

找规律

I 序列操作Ⅱ

显然,所有被查询的区间都是被修改的区间
每次进行修改操作的时候,可以顺便进行区间查询,保存下答案即可
但查询并不满足区间加法
对于每次修改,暴力的遍历,并使用𝒎𝒂𝒑统计,单次操作复杂度 $𝑶(𝒏 𝒍𝒐𝒈𝒏)$
此时用线段树维护当前区间是否被覆盖,每次修改前暴力统计,然后进行区间覆盖
显然,由于区间覆盖操作,任意修改产生的区间只会被再遍历一次,再加上使用𝒎𝒂𝒑统计
因此单次复杂度不会超过 $𝑶\left(𝒍𝒐𝒈^{2}𝒏 \right)$
看起来就是最标准的做法了
但事实真的如此吗?
引入一个该类区间覆盖操作更好用的“数据结构”——𝑶𝒍𝒅 𝑫𝒓𝒊𝒗𝒆𝒓 𝑻𝒓𝒆𝒆
对于本题,
我们合并相邻的重复区间,转化为一个有序的多元组,[l,r,val] 分别代表起点,终点,值,并保持顺序
例如:
对于一个序列 5,5,5,4,4,4,5,6,7,7
我们转化为[1,3,5],[4,6,4][7,7,5],[8,8,6],[9,10,7]
那么如何操作呢?
对于例子,我们要修改[2,9]为 1 的时候,
1. 取出[1,3,1]到[9,10,7]之间所有的元素
2. 分裂[1,3,5]和[9,10,7]两个元素,为[1,1,5],[2,3,5],[9,9,7],[10,10,7],因为该连续区间将被破坏
3. 统计[2,3,5],[4,6,4][7,7,5],[8,8,6],[9,9,7]中的所有的数据
4. 销毁[2,3,5],[4,6,4][7,7,5],[8,8,6],[9,9,7],因为他们即将被覆盖
5. 插入新的元组[2,9,1],结束操作
现在的整个元组序列就是:[1,1,5],[2,9,1],[10,10,7]
显然,单次操作的复杂度受到被访问的区间内的元素数量影响,很容易就会退化到线性
但仔细推理就能发现,
每次操作最多会产生两个元素,而每个元素最多只会被访问一次就会被销毁
因此,每次操作的均摊复杂度只受到[取出元素],[销毁元素],[插入元素],这三个操作复杂度的影响,且要有序
也就是说,我们要高效率地维护一个动态的有序序列,快速的满足上述操作
显然我指的是平衡树!
可是平衡树比线段树难写太多了吧?
但事实真的如此吗?
我们 STL 库里就有现成的平衡树给你用! 还是最强的红黑树!
Set !
对于 set,我们用二分查找取出头尾,然后分裂,然后统计后删除,再插入一个新的元素
复杂度和线段树一样优美, 一气呵成!