【CF809D】Hitchhiking in the Baltic States

题意:

给你n个区间[li,ri],让你选出从中一个子序列,然后在子序列的每个区间里都选择一个tj,满足t1<t2<...<tlent1<t2<...<tlen。最大化这个子序列的长度。

1≤n≤3⋅105,1≤l≤r≤109

题解:

首先我们很容易想到n^2的递推式

f[i]表示最后一个是i

f[i]=max(f[i],max(f[j])+1) (l<=i<=r)

那么这样是可以O(n^2)扫一遍的

然后会发现这个东西不太好优化

我们很自然的会想到用前缀g[i] 表示最后一个<=i时

那么方程变为g[i]=max(g[i],g[i-1]+1)

然后我们发现 这不就是将这一段左移么 但是还要取个max

但是很容易发现,g[i-1]+1一定是>=g[i]的(因为上一次一定得从前面转移)

这样方程变为g[i]=g[i-1]+1

我们只需将l-r左移一格,再区间+1,再给右边那段max个g[r]

这个显然是可以平衡树来维护的

上一篇:BZOJ 2466: [中山市选2009]树( 高斯消元 )


下一篇:适用函数ALSM_EXCEL_TO_INTERNAL_TABLE把excel文件传输到内表中