BZOJ 4553 [Tjoi2016&Heoi2016] 序列

发布于 2018-01-24  152 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4553

题意:见原题面。


即\(l_i\) 为 i 能到的最小状态,\(r_i\) 为最大。

变形的 LIS,考虑一个两个相邻的状态 i 和 j 什么情况 j 能更新 i,即:

\(j< i\)

\(a_j< a_i\)

\(a_j< l_i\)

\(r_j< a_i\)

实际上发现第二条包含于三四条了。

那么三维偏序问题,写了个 CDQ 练手。由于时间比较松所以二维线段树和 2DT 也能过...

 


一个非常弱的准退役OIER