//鸣谢litble(kb)Dalao细心地为我讲解cdq分治与这道题,感激不尽啊QvQ

1. 题目

传送门= ̄ω ̄=

2. 题解

典型的cdq分治解决三维偏序问题。

首先我们时光倒流,把所有删除操作转换为插入操作

那么三维分别为:

  • 插入时间$t$
  • 插入在原序列中的位置$x$
  • 插入的值$y$

得到三元组$(t,x,y)$

首先按第一维$t$排序后跑cdq,在cdq内将第二维$x$排序,然后用树状数组维护第三维$y$,每次更新$[mid+1,r]$(右区间)内所有操作的答案。

具体,,,下次让boshiDalao写个CDQ分治的算法文章吧(也可能是我写),这里不做过多赘述。

先贴代码啦(爸妈催ing)