这题卡莫队吗........

黄一肯 发表于 2个月前 · 关联问题 相同物品

lr580 发表于 2个月前

不造(没学莫队,我太蒟蒻了

//但是分块n sqrt{n}的复杂度过5e5可能真的不大行? (都3.5e8了)

 

 

 

一种能过的解法是线段树,每个点存储的信息是 第i个柜子的物品编号上一次出现的柜子下标 (实际上就是编号为a[i]的双向链表的prev指针),线段区间就维护上述信息的max值 (维护区间最值)。

单点删除需要对双向链表删除节点,并更新线段树对应维护的内容。

区间查询就输出线段树维护的区间最值即可。

//如果上述解法描述有误欢迎指正qwq

黄一肯 发表于 2个月前

太强了!!而且讲的很清晰!!谢谢大佬!!!

abcdefg 发表于 23天前