牛客寒假集训营第三场E线段树+链表
题目
有$n$个礼物,每个礼物都有一个编号,有两种操作:
- 拿走位置$i$的礼物
- 查询区间[l,r]有没有两个编号相同的礼物
题解
对于每个位置$i$,维护两个信息:
$last[i]$:表示上一个最近的$a_i$的位置,如果没有置为$0$
$next[i]$:表示下一个最近的$a_i$的位置,如果没有置为$n+1$
这样,就形成了一个链表式的结构。
- 拿走位置$i$的物品,只需做类似于链表的删除操作即可。
- 查询区间[l,r]是否有两个物品,也就是查询区间内是否存在$last[i]>=l$。
代码
1 | /* |