2019年9月
[学习笔记]尺取法维护不支持删除的信息
上午模拟赛考了这个trick,然后我不会,学会了来写一波博客。
考虑一类求最短区间的问题,满足单调性(可以two-pointers),插入很快,但是删除很慢,不过可以快速的判断两段的信息合并能否满足条件。
这时普通的尺取法就没法用了。
怎么解决呢?
上午模拟赛考了这个trick,然后我不会,学会了来写一波博客。
考虑一类求最短区间的问题,满足单调性(可以two-pointers),插入很快,但是删除很慢,不过可以快速的判断两段的信息合并能否满足条件。
这时普通的尺取法就没法用了。
怎么解决呢?