「北大集训 2021」魔塔 OL | CTT2022 D1 T2

题目大意

维护 \(q\) 个操作：

1. 在序列末尾新增一个点 \((x,y,z)\) ，其权值为 \((a,b)\) 。

2. 删除序列中编号为 \(k\) 的点（不影响其他点编号）。

3. 仅保留序列中三维分别在 \(g,l,d\) 以内的点，做询问：

   每一个点是一只怪物，击杀他需要 \(a\) 的血量，击杀后会恢复 \(b\) 的血量。

   求击杀当前序列中所有怪物需要的最少初始血量。

简要分析

先不考虑三维偏序的部分，对于序列 \(a_i,b_i\) 做贪心：

考虑相邻交换，若交换 \(i,j\ (j=i+1)\) 更优，则满足： \[ \max\{a_i,a_j+a_i-b_i\}>\max\{a_j,a_i+a_j-b_j\} \\ 即 (a_i>a_j \and a_i>a_i+a_j-b_j) \or (a_j+a_i-b_i>a_j \and a_j+a_i-b_i>a_i+a_j-b_j) \\ 即 (a_j-b_j<0 \and a_i>a_j) \or (a_i-b_i>0 \and b_j>b_i) \] 具体排序方式即：

1. \(a_i-b_i<0\) 的放在前面，按照 \(a_i>a_j\) 排序。
2. \(a_i-b_i>0\) 的放在后面，按照 \(b_j>b_i\) 排序。

连续的二元组 \((a_i,b_i)\) 容易合并为 \((a',b')\) ，分别为：最大值，总和。

离线所有点，按照上述方式排序，将得到的序列每 \(B\) 个分一块，每一个块维护所有 \(2^B\) 种情况对应的二元组和。

对于第 \(i\) 个块，维护 \(3\) 组集合：

1. \(x\leq u\) 的集合 \(A_{i,u}\) 。
2. \(y\leq v\) 的集合 \(B_{i,v}\) 。
3. \(z\leq w\) 的集合 \(C_{i,w}\) 。

在操作时，动态维护集合 \(S\) 表示当前在整个序列里的点。

查询时对于每一个块，求出 \(S\ \cap A_{i,g}\ \cap B_{i,l}\ \cap C_{i,d}\) ，然后处理对应集合。

设 \(n\) 为怪物总数， \(x\) 为三维的值域，复杂度为 \(O(n\log n+\frac{nx}{B}+\frac{n\cdot 2^B}{B}+q\frac{n}{B})\)

\(B\) 大致取 \(\log n\) 即可。

ans[i]=(a,b)

[i,i+B)