Data Structures

The logarithmic method is a classical static-to-dynamic transformation: it stores one dynamic ordered set as several immutable static components and rebuilds them by merges. The same component-and-merge discipline underlies write-optimized ordered indexes, where cheap insertions must be reconciled with exact ordered queries. In this paper, we study the insertion-only version after $n$ insertions, over abstract keys, in a strongly materialized merge-stack model with sequential component merges and one forward scan of the live components per query. We bound the product between the total amount of data written during the $n$ insertions and the worst-case amount of data read by a single query, known as the write-read product. The optimal bounds are as follows:

• Membership and local certificates: $\Theta(n\log^2 n)$.
• Order and range queries with named keys or endpoints: $\Theta(n\log^3 n)$.
• Select: $\Theta(n^2)$.

Thus, the logarithmic method does not impose a universal dynamic overhead: under materialized one-way access, the optimum depends on what information the query reveals before the scan starts. This pinpoints the access-model obstruction behind the extra logarithm for exact order and range queries, and the quadratic barrier for select.

存在初始为空的点集 \(S\), 进行 \(n\) 次操作, 形如:

\(n \leqslant 2 \times 10^{5}, k, u \leqslant 10^{18}\).

扫描线模板题，从小到大枚举横线的纵坐标，枚举到矩形下界就给这条边的左右端点构成的区间 \(+1\)，否则 \(-1\)，用线段树维护，当前线段树有值的结点个数就是这个纵坐标的贡献。

当然，本题还需要动态开点，所以需要维护区间内有效点的数量。

考虑用扫描线，维护区间最大值即可。

考虑一些在序列上的区间操作，如区间加和区间求和。

直接暴力做单次操作复杂度是 \(\Theta(n)\)，总时间复杂度 \(\Theta(qn)\).

具体实现如下：

对每个块维护整块加的值，查询的时候加上即可。

时间复杂度 \(\Theta(n\sqrt{n})\)。

并查集可以用来维护一类具有传递性的关系，维护形如将 \(x\) 与 \(y\) 所在集合合并和询问 \(x\) 和 \(y\) 是否在同一个集合的操作。

对于普通并查集来说，有路径压缩和按秩合并等优化，路径压缩一般实现如下 ：

按秩合并则取点数小的连向点数大的即可。

顾名思义，字典树就是支持像字典一样加入和查询字符串的树形数据结构，实现如下：

在很多问题中，字符串仅由 \(0\) 和 \(1\) 构成，这些问题存在一定的共性。

考虑如下问题，给一些数，维护它们的异或和，支持插入，删除和全局 \(+1\)。

与线段树合并类似，实现如下：