摘要
Pickupwin 写下了 DP 转移式,略作变形,发现事情十分简单
题面
解
$$
F_i=F_j+Val(j,i)
$$
$$
F_i=F_j+[2(Cnt_i-Cnt_j)\geq i-j]
$$
$$
F_i=F_j+[(2Cnt_i-i)\geq (2Cnt_j-j)]
$$
以 $2Cnt_i-i$ 为下标维护线段树,树内只记录符合要求的 $j$
询问就是两个区间 $max$
由于是取 $max$ 所以要让两两下标不同(不然删除麻烦一点),用 stable_sort 离散化
Code
1 |
|