辛集市住房和城乡建设局网站,网站开发前端技术趋势,网络营销推广的八大核心能力,网站建设推广有没有这里写自定义目录标题 题目分析代码思路 题目分析 n,m都是 1 0 5 10^5 105 #xff0c;需要将时间复杂度控制在 n log n n \log n nlogn以内。 如果有两次连续的前缀操作#xff0c;由于它们都是降序排列#xff0c;等价于只做第二次排列#xff0c;忽略掉第一次。 同… 这里写自定义目录标题 题目分析代码思路 题目分析 n,m都是 1 0 5 10^5 105 需要将时间复杂度控制在 n log n n \log n nlogn以内。 如果有两次连续的前缀操作由于它们都是降序排列等价于只做第二次排列忽略掉第一次。 同样是前缀如果前一次比后一次长第二次也不需要排了。因为都是降序它本来就是有序的。 因此连续的前缀操作只要保持最长的即可。 题目原始序列是一个升序序列那么第一个有效操作必须是前缀操作即降序。且有序操作必定是交替进行的。 所有有效操作区间必定是严格变小的。 线段树和pair都可以。但线段树没有必要。
代码思路
如果p为0则是前缀操作只保留一个最大的即可。 且需要考虑如果非连续要删掉所有比当前小的前面操作。 如果后缀操作 如果连续选最小的即保留最长的即可。同理需要删掉所有比当前小的后缀操作。然后记录当前操作。
然后从前往后处理所有保留的操作。
