BZOJ 4553 [Tjoi2016&Heoi2016] 序列


题目链接: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 也能过...

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4553 [Tjoi2016&Heoi2016] 序列


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,