F
会了,显然 xxx,yyy 是上升的,考虑维护两个线程一个一个记录最大值,一个存普通值求 LISLISLIS,我们会发现只要出现一个能更新最大值的数就一定要更新,否则一定不优
证明:令当前两个线程为 (Ma,P)(Ma,P)(Ma,P),考虑新加进来一个数 XXX,考虑两种情况,两个策略:
1. X>MaX>MaX>Ma
* A:更新最大值,变为 (X,P)(X,P)(X,P),ans+1ans+1ans+1
* B:放到普通数组里,变为 (M,X)(M,X)(M,X),ans+1ans+1ans+1
* 对比:发现因为递增,显然 X>PX>PX>P,在后续答案的更新上显然不优
2. X≤MaX\le MaX≤Ma
* A:很显然丢到这无法使答案增加
* B:而放到普通数组里去影响 LIS 显然更好
由此这种做法是对的
时间复杂度瓶颈 O(nlogn)O(n \log n)O(nlogn) 求 LISLISLIS