本文从WordPress迁移而来, 查看全部WordPress迁移文章
线段树
三鲜图灵树
主要是离线处理。另外要记录每个数字上一次出现的位置,但是数字太大,达到1000000000,所以没办法直接开一个pre[m]数组去记录,所以映射一下(离散化), 因为最多只有30000个数字
把所有询问读入,按右端点升序排序,然后只需要扫一遍原序列
每扫到一个数字,看看它之前是否出现过,在它上一次出现的位置删除它,然后在当前位置插入它。然后看看这个位置是否是某些询问的右端点,是的话把右端点为该点的询问全部回答。
离散化的这题没怎么应用,就是在判断一个数字是否出现时用了一下
所以说白了就是单点更新(插入,删除),区间求和
这个东西,树状数组做起来容易很多,所以就用树状数组写了,虽然是线段树的题,但线段树应该是比树状数组慢一点的,另外编程复杂度肯定高
1 |
|