题意

支持三个操作:

  • 在 \(t\) 时刻给 multiset 加入一个元素 \(x\)
  • 在 \(t\) 时刻给 multiset 删除一个元素 \(x\)
  • 询问 \(t\) 时刻 multiset 里元素 \(x\) 的个数

可以通过时光机来回穿梭,要按照给出的顺序操作

分析

三维偏序的简单题

第一位是题目给出的操作顺序,第二维是时间,第三维是元素 \(x\)

按照题目给出的操作顺序分治,每次考虑处理左边的操作对右边询问的影响

利用分治的同时用归并排序对第二维进行排序,于是只需要考虑排在右边的询问前面的左边的操作

直接用 map 暴力操作即可

 

Categories: CDQ 分治

发表评论

电子邮件地址不会被公开。 必填项已用*标注