单调栈+离散化 可行否?

P2471 [SCOI2007] 降雨量

可行 若lg[x]表示x左边第一个大于等于x的数,rg表示x右边第一个大于等于x的数 1.利用单调栈得到lg,rg 2.分类讨论 2.1先判断true的情况,仅当x到y之间所有的年份降雨量已知,并且lg[x] == y时,得到ture. 2.2其次判断false的情况, 2.2.1 x,y均已知,若lg[x]!=y,则false 2.2.2 x已知,y未知,若lg[x]>y,则false 2.2.3 x未知,y已知,若rg[y]<x,则false(与情况2对称) 2.3 若既不是true,也不是false,则为maybe
by WangZaiaw @ 2024-01-10 22:11:48


@[WangZaiaw](/user/996679) 其实和线段树维护差别不大、
by Mu_leaf @ 2024-05-13 16:31:28


|