D

手机里有n张照片,向左向右切换(1向左边为n)一张的代价为a,浏览的代价为1,一些照片若浏览需要旋转,代价为b,浏览过的照片可以跳过(即不用浏览),最开始在第一张照片,求在给定的T内,最多能浏览几张照片。

暴力+二分
通过观察发现浏览的照片为前缀+后缀的形式,分别枚举前缀和后缀,然后二分后缀和/前缀和,找到最大能到达的位置

E

一个n*m的矩阵,替换其中的数,使得每行/每列的数的大小关系不变,使得最大的数最小。

幷查集
很容易想到从1开始向矩阵中添加数字,当前位置的数即所在行和列的最大值+1
但是同一行和同一列遇到相同的数时,就要同时处理,这个可以用并查集

F

给定一个长度为n(4e5)的序列,给定m(4e5)个询问
每个询问输出替换第a个位置为b后的LIS长度
询问间不互相影响

DP

考虑替换的位置,若当前位置为关键位置(即去掉它LIS长度会减少),则答案最小值为|LIS|-1,否则为|LIS|
d1[i] 表示以i结尾的 LIS,d2[i] 表示以i开头的 LIS (或者从结尾到i 的LDS)
若$d1[i] + d2[i] - 1 = |LIS|$,且$(d1[i],d2[i])$只出现一次,则说明它是关键位置

对于替换后的答案考虑离线,按顺序排序后,用普通的求LIS的方法求
d3[i] 表示以i个询问位置结尾的 LIS,d4[i] 表示以i个询问位置开头的 LIS

p.s. 若互相影响也是可以求的