UOJ Logo return20071007的博客

博客

一种简单的 $O(n)-O(\alpha(n))$ 静态区间半群信息查询在线算法

2024-10-26 19:29:43 By return20071007

省流:静态区间半群信息查询的在线 $O(n)-O(\alpha(n))$ 简单算法(核心代码 1.6k)。

众所周知静态区间半群信息查询的正常做法有一个在线的 $O(n)-O(\alpha(n))$ 做法,但那个东西十分的不 practical。我们这里提出一种 $O(n)-O(\alpha(n))$ 的简单算法来解决这个问题。默认读者已经掌握了 zkw 线段树。

考察 zkw 线段树的查询结构(左闭右开 0-index 区间):先将 l 加上 M,再将 r 加上 M+1,随后重复以下流程直到 lr 成为兄弟,每次结束后将 lr 减半:若 l 为偶数则将其兄弟置入贡献节点左序列的末端,若 r 为奇数则将其兄弟置于贡献节点右序列的首段。最后拼接左右贡献序列,我们即按序得到了所有的贡献节点,将其从左至右累计贡献即可。如果写过 zkw 线段树的代码,这段应当不难理解。

不难注意到,zkw 线段树堆式存储的特性为我们带来了另一条优秀性质:叶子 l 与叶子 r(保证其不相同且不为兄弟)的 lca 的两个儿子分别为 l>>__lg(l^r)r>>__lg(l^r),且这两个节点是兄弟。证明就是考虑这俩的 lcp 之后的长度是 __lg(l^r)。我们同时考虑,对于同一个节点作为路径上的 lr 存在,它能造成的贡献各自是固定的。以 l 为例,若这个节点编号是奇数则没有贡献,否则是其兄弟的值。于是我们把一个节点的两种贡献打包成一个 pair(注意两项转移顺序一正一反),然后问题转化为线段树上叶子到某个已知的祖先(不含)的路径查半群。

我们这里定义:

$$\large{A(c,i,j)=}\begin{cases} j+1&if\ c=1\ and\ i=0\\[8pt] A(j,i-1,A(1,i-1,j))&if\ c=1\ and\ i>0\\[8pt] A(c-1,i,A(1,i,j))&if\ c>1\\[8pt] \end{cases}$$

人话就是把阿克曼函数迭代了 $c$ 次。这里我们要求 $1\le c\le j$。

我们不难观察到对于任意 $p\ge 1$,存在 $n$ 与 $x_1=1\lt x_2\lt\cdots\lt x_{n+1}=p$ 且存在 $b_1\gt b_2\gt\cdots\gt b_n$ 与 $1\le c_1,c_2,\cdots,c_n$ 满足 $x_{i+1}=A(c_i,b_i,x_i)$,且对于任意 $1\le i\le n$ 均有 $1\le c_i\le x_i$ 成立。证明的话对 $b$ 贪心即可。定义 $\alpha(p)$ 是满足 $A(1,i,1)\gt p$ 的最小整数值,那么不难发现 $0\le b_i\lt \alpha(p)$。换而言之,如果我们取所有如上合法的 $[x,A(c,b,x))$ 为区间,那我们可以将任何前缀用 $\alpha$ 个区间拼起来。

让我们回到原问题。重新定义一个线段树上节点到最近叶子的距离加一为其“高度”。我们对一个高度为 $h$ 的点维护所有,合法的、其上节点高度构成连续 $[h,A(c,b,h))$ 的、从这个点出发向根的,链上的半群。这个东西是显然可以用阿克曼定义式来递推的。

接着来算这个东西的状态数。我们的 $c$ 只有 $O(h)$ 种,$b$ 只有 $O(\alpha(n))$ 种(其实是 $\alpha(\log_2n)$ 种,但这俩同阶),于是总状态数的规模在 $\alpha(n)$ 倍所有节点高度和,而后者熟知是线性的,所以总的状态数是 $O(n\alpha(n))$ 的,于是预处理和空间复杂度显然是 $O(n\alpha(n))$ 的。至于查询,我们注意到高度构成的前缀本质上只有 $O(\log_2n)$ 种,全部预处理出来贪心拆,于是查询复杂度就是 $O(\alpha(n))$ 的了。

于是我们得到了一个 $O(n\alpha(n))-O(\alpha(n))$ 的算法。但不难注意到这个东西的空间和预处理都不是很牛,于是我们在底层悄咪咪套一层 $O(\alpha(n))$ 的分块,然后就变成 $O(n)-O(\alpha(n))$ 了。做完。

这里挂个板子吧。应该很清楚:预处理阿克曼和前缀拆分,建线段树和结构,查询。两个小细节:我们其实在代码里并不需要处理三维阿克曼的值,只算 $c=1$ 即可;我们可以在算阿克曼函数的时候进行上界截断,反正这玩意要多大都没意义。

constexpr struct ACK_PRECALCER {
  constexpr static int A = 3, H = 30;
  int Ack[A][H];
  tuple<int, int, int> pos[H][A];
  span<tuple<int, int, int>> pth[H];
  constexpr ACK_PRECALCER() {
    iota(Ack[0], Ack[0] + H, 1);
    for (int i = 1; i < A; ++i)
      for (int j = 0; j < H; ++j)
        for (int T = j + 1, &x = Ack[i][j] = j; T && x < H; --T)
          x = Ack[i - 1][x];
    for (int j = 1; j < H; ++j) {
      int i = 1, x = A - 1, t = 0;
      while (i < j) {
        while (Ack[x][i] > j) --x;
        int k = i - 1, c = -1;
        while (Ack[x][i] <= j) i = Ack[x][i], ++c;
        pos[j][t++] = {k, x, c};
      }
      pth[j] = span(pos[j], t);
    }
  }
} Ack;
template <class S, auto op, auto e>
  requires is_convertible_v<decltype(op), function<S(S, S)>> &&
           is_convertible_v<decltype(e), function<S()>>
class uttree {
  constexpr static int A = ACK_PRECALCER::A, B = (A + 1) << 1;
  typedef pair<S, S> S_p;
  static S_p op_p(S_p x, S_p y) {
    return {op(x.first, y.first), op(y.second, x.second)};
  }
  vector<S> val, pre, suf;
  vector<array<vector<S_p>, A>> tog;

 public:
  void build(const vector<S>& v) {
    int n = v.size();
    val = pre = suf = v;
    for (int i = 1; i < n; ++i)
      if (i % B) pre[i] = op(pre[i - 1], pre[i]);
    for (int i = n - 1; i; --i)
      if (i % B) suf[i - 1] = op(suf[i - 1], suf[i]);
    if (n <= (B << 1)) return;
    int N = (n - 1) / B, H = __lg(N) + 1, M = 1 << H++;
    vector<S> zkw(M << 1, e());
    for (int i = 1, j = B; i < N; ++i, j += B)
      zkw[i | M] = accumulate(val.data() + j, val.data() + j + B, e(), op);
    for (int i = M - 1; i; --i) zkw[i] = op(zkw[i << 1], zkw[i << 1 | 1]);
    tog.resize(M << 1);
    for (int h = H - 2, s = 4; s <= M; s <<= 1, --h)
      for (int x = s; x < (s << 1); ++x)
        for (int i = 0; i < A; ++i)
          for (int y = h, c = 0; (y = Ack.Ack[i][y]) < H && c < h; ++c)
            tog[x][i].push_back(
                c ? op_p(tog[x][i][0], tog[x >> (Ack.Ack[i][h] - h)][i][c - 1])
                : i     ? op_p(tog[x][i - 1][0],
                               tog[x >> (Ack.Ack[i - 1][h] - h)][i - 1][h - 1])
                : x & 1 ? pair{e(), zkw[x ^ 1]}
                        : pair{zkw[x ^ 1], e()});
  }
  S query(int l, int r) const {
    if (l / B >= --r / B)
      return accumulate(val.data() + l, val.data() + r + 1, e(), op);
    S L = suf[l], R = pre[r];
    if (int M = tog.size() >> 1; (l = l / B | M) + 1 < (r = r / B | M))
      for (auto [j, x, y] : Ack.pth[__lg(l ^ r) + 1])
        L = op(L, tog[l >> j][x][y].first), R = op(tog[r >> j][x][y].second, R);
    return op(L, R);
  }
  uttree() {}
  explicit uttree(const vector<S>& v) { build(v); }
};

可以用 GBST 或树剖上树,懒得搞了。对高度的定义略加修改可以把 $\alpha$ 搞成双参,同懒。

以上。

一种简单的 $O(n\alpha(n))$ 静态区间半群信息查询离线算法

2024-10-19 08:08:37 By return20071007

省流:静态区间半群信息查询的离线 $O(n\alpha(n))$ 简单算法(核心代码 1.2k,默认 $n,m$ 同阶)。

众所周知静态区间半群信息查询的正常做法有一个在线的 $O(n\alpha(n))$ 做法,但那个东西十分的不 practical,同时空间也有点危险。如果允许离线,我们有一个扫描线+并查集的简单做法,但那个做法的复杂度是 $O(n\log n)$(元素顺序有要求导致无法按秩),实测也跑得不快。我们这里提出一种 $O(n\alpha(n))$ 的简单算法来解决这个问题。默认读者已经掌握了带权并查集和 zkw 线段树。

考察 zkw 线段树的查询结构(左闭右开 0-index 区间):先将 l 加上 M,再将 r 加上 M+1,随后重复以下流程直到 lr 成为兄弟,每次结束后将 lr 减半:若 l 为偶数则将其兄弟置入贡献节点左序列的末端,若 r 为奇数则将其兄弟置于贡献节点右序列的首段。最后拼接左右贡献序列,我们即按序得到了所有的贡献节点,将其从左至右累计贡献即可。如果写过 zkw 线段树的代码,这段应当不难理解。

不难注意到,zkw 线段树堆式存储的特性为我们带来了另一条优秀性质:叶子 l 与叶子 r(保证其不相同且不为兄弟)的 lca 的两个儿子分别为 l>>__lg(l^r)r>>__lg(l^r),且这两个节点是兄弟。证明就是考虑这俩的 lcp 之后的长度是 __lg(l^r)。我们同时考虑,对于同一个节点作为路径上的 lr 存在,它能造成的贡献各自是固定的。以 l 为例,若这个节点编号是奇数则没有贡献,否则是其兄弟的值。于是我们把一个节点的两种贡献打包成一个 pair(注意两项转移顺序一正一反),然后问题转化为线段树上叶子到某个已知的祖先(不含)的路径查半群。线段树的性质实在有点美妙,我们可以倒序枚举祖先然后用带权并查集处理这个东西,动态把每个点和爹连起来就行。注意一个细节:由于我们本质上是要找一个拓扑序,而同层节点之间没有祖孙关系,我们可以把 lr 一起挂到深度上然后以层为单位处理,当然这个搞不搞都意义不大。

兜兜转转最后还是绕回了我们的并查集算法,那么它的复杂度为什么是对的呢?我们参考 OI-wiki 上的并查集复杂度证明,发现单路压所缺失的那个秩,它一共只有以下几个事情:

  1. 每次合并至多只有一个点的秩上升,且至多上升 1。

  2. 节点的秩不减。

  3. 一个点父亲的秩至少比自己的秩大一。

  4. 初始时,每个点会给势能带来 $\alpha(n)$ 倍秩的贡献。

我们充分发扬人类智慧,直接在线段树上取一个点到最近的叶子的距离作为秩锁死,来验证一下上面几条:

1,2:秩根本没变。

3:一个节点的父亲一定是某个祖先(因为每次连边都是一个点连它爹),到叶子的距离一定更大。

4:设底层有 $n=2^h$ 个节点,那总秩为 $\sum_{i=0}^h(i\times2^{h-i})=\sum_{i=0}^{h-1}\sum_{j=0}^{i}2^j=\sum_{i=1}^{h}(2^i-1)=2^{h+1}-h-2=O(n)$,于是初始势能正确。

于是我们证明了这个东西的复杂度是正确的!代码非常好写。

#if __cplusplus >= 202002L
#define TEMPLATE                                                  \
  template <class S, auto op, auto e>                             \
    requires is_convertible_v<decltype(op), function<S(S, S)>> && \
             is_convertible_v<decltype(e), function<S()>>
#else
#define TEMPLATE template <class S, S (*op)(S, S), S (*e)()>
#endif
TEMPLATE class uttree {
  typedef pair<S, S> S_p;
  static auto e_p() { return make_pair(e(), e()); }
  static auto op_p(S_p x, S_p y) {
    return make_pair(op(x.first, y.first), op(y.second, x.second));
  }
  vector<S_p> sgt;

 public:
  void build(const vector<S>& v) {
    int n = v.size(), M = 1 << (__lg(n + 1) + 1);
    sgt.resize(M << 1, e_p());
    auto vi = [&](int i) -> S& {
      return i & 1 ? sgt[i ^ 1].first : sgt[i ^ 1].second;
    };
    for (int i = 1; i <= n; ++i) vi(i + M) = v[i - 1];
    for (int i = M - 1; i > 1; --i)
      vi(i) = op(sgt[i << 1 | 1].second, sgt[i << 1].first);
  }
  uttree() {}
  explicit uttree(const vector<S>& v) { build(v); }
  vector<S> operator()(const vector<pair<int, int>>& q) const {
    if (q.empty()) return {};
    int n = q.size(), M = sgt.size() >> 1, h = __lg(M);
    vector<vector<int>> tog(h);
    vector<int> fa(M << 1, -1);
    vector<S_p> fv(M << 1, e_p());
    vector<S> ans(n, e());
    for (int i = 0; i < n; ++i) {
      int l = q[i].first + M, r = q[i].second + M + 1;
      tog[__lg(l ^ r)].push_back(i);
    }
    auto findf = [&](auto&& self, int x) {
      int f = fa[x];
      if (!~f) return x;
      fa[x] = self(self, f);
      fv[x] = op_p(fv[x], fv[f]);
      return fa[x];
    };
    for (int z = h; z; --z) {
      for (int i : tog[h - z]) {
        int l = q[i].first + M, r = q[i].second + M + 1;
        findf(findf, l), findf(findf, r);
        ans[i] = op(fv[l].first, fv[r].second);
      }
      for (int x = 1 << z; x < (1 << (z + 1)); ++x)
        fa[x] = x >> 1, fv[x] = sgt[x];
    }
    return ans;
  }
};
TEMPLATE vector<S> query(const vector<S>& v, const vector<pair<int, int>>& q) {
  return uttree<S, op, e>{v}(q);
}

以上。精细复杂度分析可以进一步说明复杂度是 $O((n+m)\alpha(m,n))$ 的,不再赘述。


发出一天后 @critnos 指出这东西可以上树,咕了几天之后 ut 把代码写了出来,这里是一篇介绍。(不过上树方式其实不太一样?)方便起见,本文考虑的是静态树上路径半群,信息在点上。边没啥区别。

这里提一嘴 cnos 的原始方案吧,就是注意到线段树的架构只要是个比较正常的平衡的二叉树都可以,于是我们直接换成 GBST 莽上去,就可以了。这个东西的问题是细节高低有点烦人……于是 ut 选择了一种码量更大但是思路更加自然的做法。

我们对树进行重链剖分。对每个点连边到链顶的父亲连边构成新树,边权是自己到链顶所有信息复合起来。不难注意到两边走到同一条链上之后就只剩一个区间,化归为链上的问题。

好那么我们考虑怎么直接通过这棵新树来定位这俩点。如果两个查询点在新树上存在祖先-后代关系直接定位完了,否则考虑其各自到 lca 前的最后一个祖先,如果它们在同一重链上就是这俩;否则,说明这俩在进同一条重链的时候正好进到了同一个点,需要的信息就是这个点的点权,也不需要再查了。至于这俩祖先的定位和各自的路径信息,我们可以小改一下求 LCA 的那个 Tarjan 算法,带个权就能做了。

兜兜转转绕回了和原树上 Tarjan 差不多的东西,于是保留节目之复杂度证明。我们定义一个点的秩固定为其在新树上到最远的叶子的距离(从 0 开始)。那么我们只需要证明初始全局秩和是 $O(n)$ 的就可以了。

我们归纳证明这个事情:对于秩为 $h$ 的点,其在原树上的子树大小至少为 $2^{h+1}-1$。比较平凡,在此略去。于是我们不难注意到一个秩为 $h$ 的点去掉重儿子后的子树大小至少为 $2^h$,称这些点属于这个秩为 $h$ 的点的“管辖范围”。不难注意到等秩的不同点“管辖范围”不交(否则在新树上一定有一个是另一个的祖先,与“等秩”矛盾),于是这样的点数至多有 $\frac n{2^h}$,然后就可以类似线段树证了。

代码……额不太短,但依然比较好写,ut 过编后板子一个字节都没改就过了。另外需要去上一篇里把那个序列板子薅过来。

这次真不如 Tarjan 快了。

TEMPLATE class uttree_hlc_node {
  typedef pair<S, S> S_p;
  static S_p e_p() { return make_pair(e(), e()); }
  static S_p op_p(S_p x, S_p y) {
    return make_pair(op(x.first, y.first), op(y.second, x.second));
  }
  static S op3(S x, S y, S z) { return op(op(x, y), z); }
  uttree<S_p, uttree_hlc_node<S, op, e>::op_p, uttree_hlc_node<S, op, e>::e_p>
      seq;
  vector<int> dfn, tf, top;
  vector<vector<int>> es;
  vector<S> vl;
  vector<S_p> fw;

 public:
  void build(const vector<pair<int, int>>& v, const vector<S>& cv) {
    int n = (vl = cv).size();
    tf.resize(n), dfn.resize(n), top.resize(n);
    es.resize(n + 1), fw.resize(n, e_p());
    for (auto p : v) {
      int u = p.first, v = p.second;
      es[u].push_back(v), es[v].push_back(u);
    }
    vector<int> sn(n);
    auto dfs1 = [&](auto&& self, int x) -> int {
      int sx = 1, sz = 0;
      for (int y : es[x]) {
        if (y == tf[x]) continue;
        tf[y] = x;
        int sy = self(self, y);
        if (sx += sy, sy > sz) sn[x] = y, sz = sy;
      }
      return sx;
    };
    tf[0] = n, dfs1(dfs1, 0);
    int dt = 0;
    vector<S_p> vl2(n, e_p());
    auto dfs2 = [&](auto&& self, int x, int t, S_p sm) -> void {
      fw[x] = sm = op_p(vl2[dfn[x] = dt++] = make_pair(vl[x], vl[x]), sm);
      if (int z = sn[x]) {
        self(self, z, t, sm);
        for (int y : es[x])
          if (y != tf[x] && y != z) self(self, y, y, e_p());
      }
      tf[x] = tf[top[x] = t];
    };
    dfs2(dfs2, 0, 0, e_p()), seq.build(vl2);
    for (int i = 0; i < n; ++i) es[i].clear();
    for (int i = 0; i < n; ++i) es[tf[i]].push_back(i);
  }
  uttree_hlc_node() {}
  explicit uttree_hlc_node(const vector<pair<int, int>>& v,
                           const vector<S>& cv) {
    build(v, cv);
  }
  vector<S> operator()(const vector<pair<int, int>>& q) const {
    if (q.empty()) return {};
    int n = dfn.size(), m = q.size();
    vector<vector<int>> tog(n + 1);
    vector<tuple<int, S, int, S>> ans(m, make_tuple(0, e(), 0, e()));
    vector<S> res(m, e());
    for (int i = 0; i < m; ++i) {
      int x = q[i].first, y = q[i].second;
      if (x == y) {
        res[i] = vl[x];
        continue;
      }
      tog[x].push_back(i), tog[y].push_back(i);
    }
    for (bool rev : {false, true}) {
      vector<int> fa(n + 1, -1);
      vector<S_p> fv(n + 1, e_p());
      basic_string<bool> vst(n, false);
      auto findf = [&](auto&& self, int x) {
        int f = fa[x];
        if (!~f) return x;
        fa[x] = self(self, f);
        fv[x] = op_p(fv[x], fv[f]);
        return fa[x];
      };
      auto dfs = [&](auto&& self, int x) -> void {
        vst[x] = true;
        if (!rev)
          for (int y : es[x]) self(self, y);
        else
          for (auto it = es[x].rbegin(); it != es[x].rend(); ++it)
            self(self, *it);
        for (int i : tog[x]) {
          int tx = q[i].first, ty = q[i].second;
          if (x == ty && vst[tx]) {
            get<0>(ans[i]) = findf(findf, tx);
            get<1>(ans[i]) = fv[tx].first;
          }
          if (x == tx && vst[ty]) {
            get<2>(ans[i]) = findf(findf, ty);
            get<3>(ans[i]) = fv[ty].second;
          }
        }
        for (int y : es[x]) fa[y] = x, fv[y] = fw[y];
      };
      dfs(dfs, n);
    }
    vector<pair<int, int>> qry;
    for (int i = 0; i < m; ++i) {
      int x = q[i].first, y = q[i].second;
      if (x == y) continue;
      int fx = get<0>(ans[i]), fy = get<2>(ans[i]);
      S &vx = get<1>(ans[i]), &vy = get<3>(ans[i]);
      if (fx == tf[fy])
        res[i] = op3(vl[x], fw[fy].second, vy);
      else if (fy == tf[fx])
        res[i] = op3(vx, fw[fx].first, vl[y]);
      else if (top[fx] != top[fy])
        res[i] = op3(op(vx, fw[fx].first), vl[tf[fx]], op(fw[fy].second, vy));
      else {
        int l = dfn[fx], r = dfn[fy];
        if (l > r) swap(l, r);
        qry.emplace_back(l, r + 1);
      }
    }
    vector<S_p> ret = seq(qry);
    for (int i = 0, j = 0; i < m; ++i) {
      int x = q[i].first, y = q[i].second;
      if (x == y) continue;
      int fx = get<0>(ans[i]), fy = get<2>(ans[i]);
      if (fx == tf[fy] || fy == tf[fx] || top[fx] != top[fy]) continue;
      res[i] =
          op3(get<1>(ans[i]), dfn[fx] < dfn[fy] ? ret[j].first : ret[j].second,
              get<3>(ans[i]));
      ++j;
    }
    return res;
  }
};
TEMPLATE vector<S> query(const vector<pair<int, int>>& v, const vector<S>& cv,
                         const vector<pair<int, int>>& q) {
  return uttree_hlc_node<S, op, e>{v, cv}(q);
}

以上。

一种基于斜二进制的序列&树上数据结构

2024-02-24 10:31:05 By return20071007

作者自己胡的×要是重复造轮子了就当搬运吧,感觉挺适合往 OI 里搬。

本文将介绍一种可以在 $O(\log n)$ 的时间内支持单点修改区间查询,并能够在 $O(1)$ 时间内完成简单末尾追加的数据结构,与它的一点树上扩展。

注:本文中提及的“线段树”均指朴素递归线段树。序列版本不管是码长还是常数都打不过高级线段树。


  • 斜二进制

斜二进制是一种奇怪的进制。它从低到高第 $i\ge1$ 位位权为 $2^i-1$。用斜二进制表示一个数时,需要满足至多一位为二且低于此位者均为零,其余位不超过一。定义一个斜二进制数的最低有效位是它最低位值非零的位。

我们将使用一种归纳构造的方式来生成每个自然数的斜二进制分解。0 的斜二进制是 0。我们假设已经对于 $n$ 生成了它的斜二进制分解,那么 $n+1$ 的斜二进制将在此基础上进行分类:

  1. $n$ 的斜二进制分解最低有效位为二。

不妨这是第 $i$ 位,那么乘上二的位值即为 $2\times(2^i-1)=2^{i+1}-2$,再加上新多出来的一就是 $2^{i+1}-1$。于是我们清除这两位并向前一位进一即可。

  1. $n$ 的斜二进制分解最低有效位不为二。

在第一位上加一即可。

不难验证以此法生成的斜二进制分解符合它应有的性质。

这么讲可能比较抽象,我们来举点例子。

  • 0 的斜二进制是 0。

  • 1 的斜二进制是 1。因为 0 的最低有效位不为二。

  • 2 的斜二进制是 2。因为 1 的最低有效位不为二。

  • 3 的斜二进制是 10。因为 2 的最低有效位为二,向前进一。

  • 4 的斜二进制是 11。因为 10 的最低有效位不为二。

  • 5 的斜二进制是 12。因为 11 的最低有效位不为二。

  • 6 的斜二进制是 20。因为 12 的最低有效位为二,向前进一。

  • 7 的斜二进制是 100。因为 20 的最低有效位为二,向前进一。

  • 8 的斜二进制是 101。因为 100 的最低有效位不为二。

  • 9 的斜二进制是 102。因为 101 的最低有效位不为二。

  • 10 的斜二进制是 110。因为 102 的最低有效位为二,向前进一。

  • 11 的斜二进制是 111。因为 110 的最低有效位不为二。

  • 12 的斜二进制是 112。因为 111 的最低有效位不为二。

  • 13 的斜二进制是 120。因为 112 的最低有效位为二,向前进一。

总之大概就是这样。


  • 后树

一棵后树维护一个长度为 $2^n-1$ 的序列,其中 $n\ge 1$。

后树的根管辖整个区间,根的左子树是区间的前 $2^{n-1}-1$ 个元素构建的后树,右子树是区间的接下来 $2^{n-1}-1$ 个元素构建的后树。注意最后一个元素不属于任何一棵子树,它是特别的——也正因如此,我们可以将一棵后树的根编号为它最后一个元素的下标。

不难发现,如果假设整个序列从一开始编号并把后树的每个节点的斜二进制写出,那么根管辖的斜二进制区间将是 $(0,100\cdots0]$,左子树的管辖区间是 $ (0,10\cdots0]$,右子树的管辖区间是 $(10\cdots0,20\cdots0]$。我们不难证明,一个点 $i$ 为根的子树的管辖区间的左端点 $j=i-\textit{skew_lowbit}(i)$,其中 $\textit{skew_lowbit}(i)$ 表示 $i$ 在斜二进制下的最低有效位。


  • 数据结构

我们考虑将 $n$ 进行斜二进制分解并用一系列后树来维护整个序列。类似这样。

如果这里出现了文字那就是图挂了。

我们对于每个下标 $i$ 维护四个东西:

  • $a_i$:序列第 $i$ 个元素的值。

  • $\textit{tr}_i$:序列上 $(i-\textit{skew_lowbit}(i),i]$ 下标的元素合并后的结果(本质上是在后树上的子树“和”)。

  • $\textit{lb}_i$:$i-\textit{skew_lowbit}(i)$。

  • $\textit{tf}_i$:点 $i$ 在后树上的父亲(不存在则置零)。

(这几个东西在缩写之前分别是:arraytreeleft_boundtree_father。)

我们以下将对几个常见操作分别说明。以和为例。

  • 节点更新

在除了 $\textit{tr}_i$ 未知以外所有必要信息均已知的情况下计算 $\textit{tr}_i$,俗称 pushup。由于并不知道 $i$ 会有零个还是两个儿子,我们的手段相当暴力:遍历所有子树进行累和。

void pushup(int x) {
  tr[x] = a[x];
  for (int y = x - 1; tf[y] == x; y = lb[y]) tr[x] += tr[y];
}

有群 u 指出应该实现得更精细一点所以也写了一版没那么暴力的,效率差距不大:

void pushup(int x) {
  if (int p = x - 1; p == lb[x])
    tr[x] = a[x];
  else
    tr[x] = a[x] + tr[p] + tr[lb[p]];
}
  • 末尾追加

$a$ 可以直接把追加的值薅过去,$\textit{tr}$ 可以调用 pushup 处理,那么我们实际上要做的就是把 $\textit{tf}$ 和 $\textit{lb}$ 维护好。

注意到只有新加点的 $\textit{lb}$ 和它两个儿子(若有)的 $tf$ 可能需要变化,我们仿照斜二进制分解的归纳构造操作就行。对于最低有效位为二的情况,我们可以简单地找到新加点的两个儿子;对于最低有效位不为二的情况,新加点没有儿子。

获取一个数 $i$ 的斜二进制最低有效位可以直接 $i-\textit{lb}_i$ 简单处理。

void append(int x) {
  int p = n, q = lb[n++], r = lb[q];
  if (a[n] = x, !q || p - q != q - r)
    lb[n] = n - 1;
  else
    lb[tf[p] = tf[q] = n] = r;
  pushup(x);
}
  • 建立

嗯做就行。本质是挨个 append

void build() {
  for (int i = 1; i <= n; ++i) {
    int p = i - 1, q = lb[p], r = lb[q];
    if (!q || p - q != q - r)
      lb[i] = i - 1;
    else
      lb[tf[p] = tf[q] = i] = r;
    pushup(i);
  }
}
  • 单点修改。

注意到树的结构没有变化,$a$ 变化的只有被修改的位置。于是我们主要考虑 $\textit{tr}$ 的变化。注意到 $tr_i$ 受影响仅当 $i$ 是被修改位置在后树上的祖先。于是我们沿着 $\textit{tf}$ 一路往上遍历祖先就行。

下面这个例子是单点加。

void update(int x, int d) {
  for (a[x] += d; x; x = tf[x]) pushup(x);
}
  • 区间查询。

从待查区间 $[l,r]$ 的右端点 $r$ 开始向 $l$ 跳,有 $\textit{tr}$ 跳 $\textit{tr}$ 没 $\textit{tr}$ 跳 $a$ 就行。可能讲得比较抽象,下面挂个代码。标准库函数 exchange(u, v) 的含义等同于是执行 u = v 并返回执行u

int query(int l, int r) {
  int ans = 0;
  while (r >= l)
    if (int x = lb[r]; x < l - 1)
      ans += a[r--];
    else
      ans += tr[exchange(r, x)];
  return ans;
}

接下来我们证一下这个东西的复杂度。我们定义一个位置 $i$ 的高度 $h_i$ 是以它为根的后树的大小加一以二为底的对数。不难发现每个点是不超过 $O(\log n)$ 的正整数。特别地,我们定义零的高度是全局最高高度加一。

于是我们有了这么一条事情:

  • $h_{\textit{lb}_{\textit{lb}_i}}\ge h_i+1$。

写个斜二进制,这是显然的。

这条告诉我们,在 if 的第一个分支被执行到之前,$h_r$ 至多两步一升,复杂度是 $O(\log n)$ 的。

而在此之后我们又会有这么第二条事情:

  • 若 $r$ 被执行第一个分支时 $h_r=x$,那么此后 $h_r

因为 $r$ 之前最后一个满足 $h_i\ge x$ 的位置 $i$ 是 $\textit{lb}_r\lt x-1$,它不可能进入循环体。

而根据上面的第一条,走第一个分支之后,至多再走一步第二个分支,一定会再回到第一个分支(否则连走两步之后 $h_r$ 加一,与第二条矛盾)。于是我们得知,在 if 的第一个分支被执行到之后,$h_r$ 至多两步一减,复杂度是 $O(\log n)$ 的。

综上,区间查询的复杂度是 $O(\log n)$ 的。


挂个【模板】树状数组 1 的完整代码吧:

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 9;
int n, m, lb[N], tf[N], a[N], tr[N];
void pushup(int x) {
  tr[x] = a[x];
  for (int y = x - 1; tf[y] == x; y = lb[y]) tr[x] += tr[y];
}
void build() {
  for (int i = 1; i <= n; ++i) {
    int p = i - 1, q = lb[p], r = lb[q];
    if (!q || p - q != q - lb[q])
      lb[i] = i - 1;
    else
      lb[tf[p] = tf[q] = i] = r;
    pushup(i);
  }
}
void update(int x, int d) {
  for (a[x] += d; x; x = tf[x]) pushup(x);
}
int query(int l, int r) {
  int ans = 0;
  while (r >= l)
    if (int x = lb[r]; x < l - 1)
      ans += a[r--];
    else
      ans += tr[exchange(r, x)];
  return ans;
}
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  build();
  for (int op; m; --m)
    if (cin >> op; op == 1) {
      int x, d;
      cin >> x >> d;
      update(x, d);
    } else {
      int l, r;
      cin >> l >> r;
      cout << query(l, r) << '\n';
    }
  return cout << flush, 0;
}

不难发现,该算法在简洁方面对比线段树有较大优势,功能强度方面介于树状数组与线段树之间。常数应该不小。

它的作用?总之大概能提供一个新的选择吧。写起来比线段树快,比树状数组逻辑清晰(不需要前缀和差分的转)。


事实上这个东西还能上树。不难发现每个点拖一个区间这个事情可以直接挂在每个点上往祖先去拖。不难发现这样依然可以在 $O(\log n)$ 的时间内刻画出树上的一条路径。另一方面,序列上需要倍增的场景其实并不多见,即使有也许多为双向,但树上倍增一般都是往祖先,这使得它可以更好地适应形如 “找到第一个满足某条件”的祖先之类的问题。

这种数据结构的预处理时空是 $O(n)$,查询是 $O(\log n)$,同时代码相当简短,在大部分情况下可以作为树上倍增的上位替代。功能性除了支持动态加叶子是优势以外一般不如树剖,但时空常数和码量均更优(笔者个人实现的时间是树剖的三分之一),同时逻辑也更清晰。严格劣 ST 树。

初始化非常简单:

void dfs(int x) {
  int p = fa[x], q = lb[p], r = lb[q];
  lb[x] = d[p] - d[q] != d[q] - d[r] ? p : r;
  for (d[x] = d[p] + 1; int y : es[x])
    if (y != fa[x]) fa[y] = x, dfs(y);
}

这里给出一份查 LCA 的代码,不难发现略加修改即可查询静态链信息:

int lca(int u, int v) {
  if (d[u] < d[v]) swap(u, v);
  while (d[u] > d[v])
    if (d[lb[u]] < d[v])
      u = fa[u];
    else
      u = lb[u];
  while (u != v)
    if (lb[u] == lb[v])
      u = fa[u], v = fa[v];
    else
      u = lb[u], v = lb[v];
  return u;
}

同时可以看到其实逻辑和倍增是很类似的,易于配套理解。

如果要维护路径信息的话,以[JLOI2015] 城池攻占 为例,初始化稍微改一下:

void dfs(int x) {
  int p = fa[x], q = lb[p], r = lb[q];
  if (!q || d[p] - d[q] != d[q] - d[r])
    lb[x] = p, tr[x] = vl[x];
  else
    lb[x] = r, tr[x] = vl[x] + tr[p] + tr[q];
  for (d[x] = d[p] + 1; int y : es[x]) dfs(y);
}

(这题是输入每个点的爹所以向下搜不需要判。)

查询就是每次跳 $\textit{lb}$,跳不了就跳爹:

int calc(int x, int h) {
  while (x)
    if (func f = tr[x]; h >= f.xl && h <= f.xr)
      h = f(h), x = lb[x];
    else if (f = vl[x]; h >= f.xl && h <= f.xr)
      h = f(h), x = fa[x];
    else
      break;
  return x;
}

Upd on 2024.3.1:来活了,注意到 DAG 支配树需要支持的操作是动态加叶子和求 LCA,专业对口。目前是洛谷最优解。

#include <bits/stdc++.h>
using namespace std;
constexpr int S = 1 << 21, N = 65535;
char buf[S], *p1, *p2, obuf[S], *O = obuf;
inline char gc() {
  if (p1 == p2) {
    p2 = (p1 = buf) + cin.read(buf, S).gcount();
    if (p1 == p2) return EOF;
  }
  return *p1++;
}
inline int rd() {
  char ch;
  while (!isdigit(ch = gc()))
    ;
  int x = ch & 0xf;
  while (isdigit(ch = gc())) x = x * 10 + (ch & 0xf);
  return x;
}
inline void prtln(int x) {
  char s[7];
  int t = 0;
  if (!x)
    *O++ = '0';
  else {
    while (x) s[t++] = x % 10 | '0', x /= 10;
    while (t) *O++ = s[--t];
  }
  *O++ = '\n';
}
basic_string<int> es[N];
int n, fa[N], d[N], lb[N], dg[N], sz[N];
inline void lca(int& u, int v) {
  if (!~u) return u = v, void();
  if (d[u] < d[v]) swap(u, v);
  while (d[u] > d[v]) d[lb[u]] < d[v] ? (u = fa[u]) : (u = lb[u]);
  while (u != v)
    lb[u] == lb[v] ? (u = fa[u], v = fa[v]) : (u = lb[u], v = lb[v]);
}
inline void addf(int x) {
  int p = fa[x], q = lb[p], r = lb[q];
  d[x] = d[p] + 1, lb[x] = d[p] - d[q] != d[q] - d[r] ? p : r;
}
inline void build() {
  memset(fa + 1, -1, n * sizeof(int));
  int q[N], l = 0, r = 0, u;
  for (int i = 1; i <= n; ++i)
    if (!dg[i]) fa[q[r++] = i] = 0, d[i] = 1;
  while (l < r)
    for (addf(u = q[l++]); int v : es[u])
      if (lca(fa[v], u), !--dg[v]) q[r++] = v;
  while (r--)
    if (int f = fa[u = q[r]]) sz[f] += sz[u] + 1;
}
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  n = rd();
  for (int i = 1; i <= n; ++i)
    while (int j = rd()) es[j].push_back(i), ++dg[i];
  build(), for_each_n(sz + 1, n, prtln);
  return cout.write(obuf, O - obuf).flush(), 0;
}

Upd on 2024.4.10:整了个例题 https://www.luogu.com.cn/problem/U421630


同时这个东西还可以用来写全局平衡二叉树。但这个时候我们会意识到一个很难受的事情:根的位置被固定了,无法再保证每个点子树大小和父亲的关系。但是这个事情我们魔怔一下就能解决:把本来的左右儿子之间插一个中儿子就行,等于是一个点有仨儿子,其中中间那个的子树大小为一。那么我们的性质就又没问题了。写出来会比朴素 GBST 稍微少一点特判。

例题:[ZJOI2008] 树的统计。写的线性建树。

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N = 3e4 + 9;
int n, m, fa[N], top[N], sn[N], sz[N], d[N], lb[N], tf[N], stk[N], sum[N], tp;
vector<int> es[N];
struct info {
  int sm, mx;
  info() : sm(0), mx(INT_MIN) {}
  info(int x) : sm(x), mx(x) {}
  info(int sm, int mx) : sm(sm), mx(mx) {}
  info& operator+=(const info& to) {
    return sm += to.sm, mx = max(mx, to.mx), *this;
  }
  info operator+(const info& to) const { return info(*this) += to; }
} a[N], tr[N];
int dfs1(int x) {
  d[x] = d[fa[x]] + 1;
  for (int y : es[x]) {
    erase(es[y], fa[y] = x);
    if (sz[x] += dfs1(y), sz[y] > sz[sn[x]]) sn[x] = y;
  }
  return ++sz[x];
}
inline void pushup(int x) {
  tr[x] = a[x];
  for (int y = fa[x]; tf[y] == x; y = lb[y]) tr[x] += tr[y];
}
int build(int l, int r) {
  int x = stk[r--];
  if (lb[x] = stk[l - 1], l <= r) {
    int i = upper_bound(sum + l, sum + r + 1, (sum[l - 1] + sum[r]) >> 1) - sum;
    int y = stk[i];
    tr[y] = a[y], lb[y] = stk[i - 1], tf[y] = x;
    l < i && (tf[build(l, i - 1)] = x), i < r && (tf[build(i + 1, r)] = x);
  }
  return pushup(x), x;
}
void dfs2(int x, int t) {
  top[stk[++tp] = x] = t, sum[tp] = sum[tp - 1] + sz[x];
  if (int z = sn[x]) {
    for (sum[tp] -= sz[z], dfs2(z, t); int y : es[x])
      if (y != z) dfs2(y, y);
  } else
    build(tp - (d[x] - d[t]), tp);
  --tp;
}
inline int lca(int u, int v) {
  while (top[u] != top[v]) {
    if (d[top[u]] < d[top[v]]) swap(u, v);
    u = fa[top[u]];
  }
  return d[u] < d[v] ? u : v;
}
inline void update(int x, int t) {
  for (a[x] = t; x; x = tf[x]) pushup(x);
}
inline info qlink(int u, int z) {
  info ans;
  while (d[u] >= z)
    if (int x = lb[u]; d[x] < z - 1)
      ans += a[exchange(u, fa[u])];
    else
      ans += tr[exchange(u, x)];
  return ans;
}
inline info query(int u, int v) {
  int z = d[lca(u, v)];
  return qlink(u, z) + qlink(v, z + 1);
}
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1, u, v; i < n; ++i)
    cin >> u >> v, es[u].push_back(v), es[v].push_back(u);
  for (int i = 1, x; i <= n; ++i) cin >> x, a[i] = x;
  dfs1(1), dfs2(1, 1);
  for (cin >> m; m; --m) {
    string s;
    int x, y;
    if (cin >> s >> x >> y, s == "CHANGE")
      update(x, y);
    else if (auto [sm, mx] = query(x, y); s == "QMAX")
      cout << mx << '\n';
    else
      cout << sm << '\n';
  }
  return cout << flush, 0;
}

Upd on 2024.3.9:

感谢 @ClHg2 的指出,直接把中儿子塞到左儿子里复杂度也是对的,因为一个点的爷爷权和一定至少是自己的两倍所以树高依然是 $\log$ 的。常数会更小一点。

改完的代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N = 3e4 + 9;
int n, m, fa[N], top[N], sn[N], sz[N], d[N], lb[N], tf[N], stk[N], sum[N], tp;
vector<int> es[N];
struct info {
  int sm, mx;
  info() : sm(0), mx(INT_MIN) {}
  info(int x) : sm(x), mx(x) {}
  info(int sm, int mx) : sm(sm), mx(mx) {}
  info& operator+=(const info& to) {
    return sm += to.sm, mx = max(mx, to.mx), *this;
  }
  info operator+(const info& to) const { return info(*this) += to; }
} a[N], tr[N];
int dfs1(int x) {
  d[x] = d[fa[x]] + 1;
  for (int y : es[x]) {
    erase(es[y], fa[y] = x);
    if (sz[x] += dfs1(y), sz[y] > sz[sn[x]]) sn[x] = y;
  }
  return ++sz[x];
}
inline void pushup(int x) {
  tr[x] = a[x];
  for (int y = fa[x]; tf[y] == x; y = lb[y]) tr[x] += tr[y];
}
int build(int l, int r) {
  int x = stk[r--];
  if (lb[x] = stk[l - 1], l <= r) {
    int i = upper_bound(sum + l, sum + r + 1, (sum[l - 1] + sum[r]) >> 1) - sum;
    tf[build(l, i)] = x, i < r && (tf[build(i + 1, r)] = x);
  }
  return pushup(x), x;
}
void dfs2(int x, int t) {
  top[stk[++tp] = x] = t, sum[tp] = sum[tp - 1] + sz[x];
  if (int z = sn[x]) {
    for (sum[tp] -= sz[z], dfs2(z, t); int y : es[x])
      if (y != z) dfs2(y, y);
  } else
    build(tp - (d[x] - d[t]), tp);
  --tp;
}
inline int lca(int u, int v) {
  while (top[u] != top[v]) {
    if (d[top[u]] < d[top[v]]) swap(u, v);
    u = fa[top[u]];
  }
  return d[u] < d[v] ? u : v;
}
inline void update(int x, int t) {
  for (a[x] = t; x; x = tf[x]) pushup(x);
}
inline info qlink(int u, int z) {
  info ans;
  while (d[u] >= z)
    if (int x = lb[u]; d[x] < z - 1)
      ans += a[exchange(u, fa[u])];
    else
      ans += tr[exchange(u, x)];
  return ans;
}
inline info query(int u, int v) {
  int z = d[lca(u, v)];
  return qlink(u, z) + qlink(v, z + 1);
}
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1, u, v; i < n; ++i)
    cin >> u >> v, es[u].push_back(v), es[v].push_back(u);
  for (int i = 1, x; i <= n; ++i) cin >> x, a[i] = x;
  dfs1(1), dfs2(1, 1);
  for (cin >> m; m; --m) {
    string s;
    int x, y;
    if (cin >> s >> x >> y, s == "CHANGE")
      update(x, y);
    else if (auto [sm, mx] = query(x, y); s == "QMAX")
      cout << mx << '\n';
    else
      cout << sm << '\n';
  }
  return cout << flush, 0;
}

具体有啥更多的应用可能还有待进一步发掘。感觉是个非常适合引入 OI 的东西,尤其是平替树上倍增的部分(?

以上。

【理性愉悦】无向连通图正整数边权线性时空单源最短路浅析

2023-09-16 22:30:03 By return20071007

作为相关 paper 的学习笔记好了。基本但不是百分百翻译论文。

前置知识:

  1. Dijkstra(下称 Dj),和其他一些同难度的基础算法。

  2. 至少一种线性树上并查集。不会的话可以看这个(如果会 Top Cluster 树分块,注意那个启发式合并改成裸的双优并查集也是对的)或者这个(0 基础也能看!!1)。

开始前提示:

  1. WRM($\omega=\Omega(\log n)$)。

  2. 线性 Dj 双向规约线性排序,这个大家还不太会,所以这个算法对 Dj 进行了一定的延展。但由于其本质上还是基于 Dj 那一套贪心思路的,我们在文章前期依然可能会用 Dj 中的相关流程来进行指代。

  3. 不保证笔者写得很顺畅,但保证一定大体能看。可能会有细节脑抽(比如把 $[v]_i$ 写成 $v[i]$),如有发现还望指出。

  4. paper 主部分有 38 个引理 7 个伪代码,作为进度条本文会在每个引理和伪代码前面给出编号。这里由于没有 paper 在解决问题之后碎碎念的一大段所以只有 37 个引理。

  5. $\subset$ 不取等号。

  6. 涉及数据结构 Q 堆(实现出来会被降格为平凡暴力数组所以不用太在意)。晚点可能补二叉堆版代码以及补那个单 $\alpha$ 但不需要原子堆的做法。

  7. 全文共 27k 文字分析纯干货,请放心食用。

SSSP,启动!


阅读更多……

【理性愉悦】如何优雅地玩转线性-常数时间复杂度

2023-07-30 22:53:04 By return20071007

本文收录部分 $\Theta(n)$ 预处理 $\Theta(1)$($\Theta(n)-\Theta(1)$)操作的强制在线算法(这个说法准确吗……反正大概就这意思啦)。

对于同一个问题可能不会收录所有算法,点名 RMQ。

基本前置:Word-RAM Model($w=\Omega(\log n)$)。


1.RMQ

世界名画。

首先我们很容易导出一个 $\Theta(n\log n)-\Theta(1)$ 的算法,用 ST 表还是二区间合并看心情。我们把原序列按 $\Theta(\log n)$ 分块,块间运行这个算法。

询问如果跨块则可以用一个后缀+块间+一个前缀拼起来,其中前后缀显然也可以 $\Theta(n)$ 预处理出来。当然如果不在意常数的话,前后缀的部分也可以一并用块内的算法运行,无妨(事实上这样比较方便在板子题测正确性)。

那么我们现在仅考虑一个块内的询问。我们考虑 RMQ 的一种 $\Theta(n)-\Theta(\log n)$ 离线算法:把询问 $[l,r]$ 按右端点排序,扫描线维护序列 $[1,r]$ 下标上的单调栈。我们发现单调栈的一个位置 $i$ 实际上代表着 $[i,r]$ 的后缀最小值在 $i$,那么我们在单调栈上二分找到第一个 $\ge l$ 的位置就可以了。我们试图把这个算法套上块。由于序列长度仅为 $O(\log n)$,我们实际上可以把每个位置的前缀单调栈压在一个二进制数里,进而把每个位置的前缀单调栈都存下来。这一步让我们不再需要离线。至于找第一个 $\ge l$ 的位置更是可以用一步位运算直接化归到找一个二进制数最低位 1 的位置,而这个是可以 $\Theta(1)$ 做的。这一步让我们撇去了复杂度里的 $\log$。

综上所述,我们现在的 RMQ 算法成功被优化成了 $\Theta(n)-\Theta(1)$。


2.LCA

常数比较好的写法是 dfs 序求 LCA,序列长度上比欧拉序求 LCA 短一倍。在此介绍一下。

考虑我们现在求 $u$ 和 $v$ 的 LCA,不妨有 $dfn_u\le dfn_v$,这里 $dfn$ 指节点的 dfs 序。

如果 $u=v$ 那么答案就是 $u$,直接判掉;否则,我们考虑 $[dfn_u+1,dfn_v]$ 这一段 dfn 上对应深度最小的节点。如果 $u$ 是 $v$ 的祖先,那么这个点一定是 $u$ 的儿子;否则,考虑从 $u$ 到 $v$ 的 dfs 过程中一定不会再经过 LCA(其在 $u$ 前已被访问),也不会跨越到 LCA 的子树之外。考虑到 $u$ 与 $v$ 在 LCA 的不同子树中,这部分一定会访问到 $v$ 对应子树的根(否则无法跨越到该子树内),那么这个根就是我们求出深度最小的节点。我们发现,这个节点一定是 LCA 的儿子,直接取它的父亲作为答案即可。

求区间最小深度这部分使用 RMQ 的优化,我们把 LCA 也成功优化成了 $\Theta(n)-\Theta(1)$。


3.LA

其实就是给定一棵树求给定点的给定级祖先。根据长链剖分那一套理论我们有一个简单的 $O(n\log n)-\Theta(1)$ 算法。我们简单优化一下这个东西并把它改成 $O(p\log n)-\Theta(1)$ 的,其中 $p$ 是树的叶子数。考虑到我们唯一更改的其实是只需要维护每个叶子的二的幂级祖先,这个我们在 dfs 的过程中维护一个祖先栈并在访问到叶子时直接根据下标找祖先即可。

这里我们介绍一个有趣的东西:ART Decomposition。简单来说,这个算法对树进行分解。考虑每个极高(自身满足且父亲不满足或没有父亲)点满足其子树有 $O(B)$ 个节点,那么很显然所有这些被取出的子树两两无交。把所有这些子树从原树上删去,那么新树的叶子必然满足原来子树内有 $\Omega(B)$ 个点,那么新树有 $O(\frac nB)$ 个叶子。我们取 $B=\Theta(\log n)$,那么新树可以直接跑那个长剖算法,我们把问题规模实际上降低到了 $O(\log n)$。

(注意这里 ART 玩起来很舒适是因为我们的复杂度瓶颈给到了叶子数量上。如果不是这样的话,我们还需要考虑把只有一个儿子的节点和儿子压起来,并用一个链上数据结构处理压起来的链。一般而言为了复杂度考虑这部分还得再分块,而且有时需要不同的维护方法,主打的就是一个阴间。)

我们套娃一层,现在问题的规模变成了 $O(\log\log n)$。那么我们对于每个点存下它的所有祖先,这需要的二进制位数是 $O(\log\log n\log\log\log n)$ ,也即 $O(w)$ 的。接下来根据一些简单的位运算操作我们就可以在常数时间内求出 k 级祖先了。

upd on 2024.10.16:上面那个写的时候脑子不好,实际上括号序的种类数十分有限,即使带上 LA 的两个参数实际情况数也很少,可以直接预处理,不用叠层了。

我们把 LA 也成功优化成了 $\Theta(n)-\Theta(1)$。


4.UFDS(上树版)

我们现在解决这样一个问题:给定一棵树支持两种操作:连接一个点与父亲的边,或者查询两个点是否联通。

老规矩,我们先试图导出一个 $O(n\log n)-\Theta(1)$ 的算法。考虑对每个点维护其联通块编号,合并时启发式合并即可。简便起见,我们的启发式合并可以直接用度数之和,这样在树上就可以直接暴搜求 size 了。

我们考虑把树按 $\Theta(\log n)$ 分块。块间显然可以运行这个算法。至于块内,我们考虑把一个点与父亲的边状态用一个布尔值标记作为这个点的点权。我们考虑用一个联通块内最高的点作为这个联通块的根,那么一个点所在联通块的根就是最低的权为 1 的点。我们考虑把每个点按照拓扑序(具体的爱啥序啥序)排列并顺次对应给一个二进制位,这一位的值表示这个点的权值;然后我们对于每个点维护一个二进制数压缩存储块内的每一个数(拓扑序位置意义下)是否为其祖先。查询的时候把两个部分按位与然后取最高位(拓扑序最大)即可。

我们还涉及到另外一个问题:查 $u$ 和 $v$ 所在块的 LCA,以及其块与两段路径对应的临界点。我们考虑 LCA 那个算法,求出最小值所在位置附带本身 dfs 序作为第二关键字,那么求出最大 dfs 序的最小值就是 $v$ 所在块一边路径与 LCA 的临界点。至于 $u$ 的临界点,可以直接暴力反过来搞一遍,也可以求出最小 dfs 序的最小值再维护一下其左边的兄弟,没有所谓。我们把 UFDS 也成功优化成了 $\Theta(n)-\Theta(1)$。


5.SDFU(?)

标题瞎起的,本质上就是想说把 UFDS 的问题反过来:给定一棵树支持两种操作:断开一个点与父亲的边,或者查询两个点是否联通。别忘了这篇文章的大前提是强制在线。

我们发现块内并没有什么区别,我们接下来只考虑怎么导出一个 $O(n\log n)-\Theta(1)$ 的算法。我们注意到上面那个启发式合并的算法,如果我们每次能精准找到断开两部分中 size 较小的一个并重新赋联通块编号,那么我们的问题就解决了。我们考虑修改一下 dfs 的步骤:维护一个栈,每个元素有三个部分:当前点,当前点的前驱和已经搜到了这个点的哪一条出边;每一次,弹出栈顶元素,把对应出边的点(若合法)入栈,然后修改原栈顶的已搜到出边。如此一来,我们考虑直接对断开边 $(u,v)$ 的 $u$ 和 $v$ 进行一个平行的 dfs,哪边先到底哪边就 size 较小。当我们找到较小的 size 时另一边也至多搜了这个规模次,于是我们的复杂度就正确了。继续树分块,我们把 SDFU(?)也成功优化成了 $\Theta(n)-\Theta(1)$。


6.区间绝对众数

标题终于不是令人迷惑的字母缩写力(喜)。

注意这个做法依赖哈希,所以不同于其他命题,这个东西的复杂度会看起来有点蠢。不过哈希一般是可以防卡的,所以先这样吧。

我们把问题分为两部分:求值和检验。

对于求值,老规矩 $\Theta(\log n)$分块,由于摩投具有结合律所以块间可以直接猫。块内递归一层把问题规模降到 $O(\log\log n)$,注意到这时候离散化后的本质不同序列和查询只有 $O((\log\log n)^{\log\log n}\times(\log\log n)^2)=O(2^{\log\log\log n\times\log\log n}(\log\log n)^2)$ 也即 $O(n)$ 种。直接摩投预处理即可。

对于检验,就是给定 $[l,r,x]$ 判断 $x$ 是否为 $[l,r]$ 的绝对众数。我们有结论,对于给定的 $x$,其作为绝对众数出现的所有区间并集大小和是 $O(c)$ 的,其中 $c$ 为 $x$ 的出现次数。具体证明可以考虑把折线图画出来然后对于每个峰把贡献累进去然后缩掉。我们考虑如何求出这个并集。我们考虑枚举“一段并集中的极长连续段左起第一个 $x$”出现的位置 $k$,可以证明其一定是 $2i-p_i$($p_i$ 表示 $x$ 第 $i$ 次出现的位置)某个前缀最小值所在处(的 $p$)。我们注意到这个连续段的左端点一定存在一个可以实现绝对众数的区间满足其右起第一个 $x$ 出现的位置是 $k$ 开始第一个后缀最大值,而右端点对应区间右起第一个 $x$ 出现的位置是能承受的极远后缀最大值,这两部分都可以双指针维护,最后把所有区间丢一起取并(左端点天然单调)然后用一个游标维护所有并集中的极长连续段(及其左端点前一个位置)的 $x$ 出现次数的前缀和,用哈希表维护。我们意识到,如果前缀和表中查不到 $l-1$ 或者 $r$ 那么一定寄了,否则我们两个前缀和一减就可以判了。

如此一来,我们把区间绝对众数也优化成了 $\Theta(n)-\Theta(1)$,虽然是期望意义下的。


7.RMSQ

人话:区间最大子段和。

我们不妨原序列是 $A$,下标从一开始。我们首先计算其前缀和数组 $C$,规定 $C_0=0$。我们考虑对于 $C$ 的每一个位置 $i$ 求出其之前最后一个 $C$ 值不小于自己的位置 $L_i$,若不存在则记为 0。我们于是有了第一条性质:$\forall i\in[1,n],j\in(L_i,i)$ 有 $C_j\lt C_i$。我们注意到,对于子段 $[j,i]$,如果 $j\le L_i$,那么换成 $[j,L_i]$ 一定不劣,于是我们不需要考虑这样的子段对答案的可能贡献。

我们再对于每个 $i$ 预处理 $[L_i,i)$ 上 $C$ 的最小值位置加一(如果有多个,取最靠右的那一个),记作 $P_i$。我们于是有了第二条性质:$\forall i\in[1,n],j\in[P_i,i)$ 有 $C_j\gt C_{P_i-1}$。综合这两条性质我们可以推出:$\forall i\in[1,n],j\in[P_i,i)$ 有 $C_j\in(C_{P_i-1},C_i)$。

(当然 $P$ 的定义本身也带给我们一个比较显然的性质:$\forall i\in[1,n],j\in[L_i,i)$ 有 $C_j\ge C_{P_i-1}$。这个不用太过在意。)

我们再记 $M_i=C_i-C_{P_i-1}$,换而言之就是 $[P_i,i]$ 的区间和。我们注意到,对于以 $i$ 为结尾的有效子段 $[j,i]$,由于 $j\in(L_i,i]$,故其和 $C_i-C_{j-1}\le C_i-C_{P_i-1}$。也就是说,如果只是要求全局的最大子段和,我们把所有 $M$ 取 $\max$ 已经做完了。

考虑对 $[l,r]$ 区间查询的解决方案。我们考虑暂且无视 $P$ 的限制直接硬做,求出 $M_l$ 到 $M_r$ 的最大值所在位置 $i$。如果 $P_i\ge l$,那我们显然已经做完了,返回即可。否则我们即有 $P_i\lt l$。由于 $P_i\gt L_i$,我们得到 $L_i\lt l$。根据我们前面的性质,我们推得 $\forall j\in[l,i)$ 有 $C_j\lt C_i$,也就是说以 $j$ 为结尾的最大子段和一定不如改成以 $i$ 结尾,直接不考虑。对于以 $i$ 为结尾的最大子段,其左端点减一的 $C$ 值要取到最小,这是一个 RMQ 的形式,直接做掉即可。对于以 $j\in(i,r]$ 的最大子段,我们考虑 $P_j$ 的位置:

若 $P_j\le P_i$:$P_i\in[L_j,j)$,推出 $C_{P_i-1}\ge C_{P_j-1}$;$i\in(L_j,j)$,推出 $C_i\lt C_j$。进而 $M_j=C_j-C_{P_j-1}\gt C_i-C_{P_i-1}=M_i$,与 $M_i$ 的最大性矛盾。

若 $P_i\lt P_j\le i$:$i\in[P_j,j)$,推出 $C_i\gt C_{P_j-1}$;但 $P_j-1\in[P_i,i)$,推出 $C_{P_j-1}\lt C_i$,矛盾。

若 $i\lt P_j\le j$:$P_j\ge l$,这是一个合法的区间。

综上所述,对于 $j\in(i,r]$,一定有 $P_j\ge l$ 合法,直接在 $M$ 上查 RMQ 即可。

于是我们就在三次 RMQ 内解决了区间最大子段和问题。由于 RMQ 已经是 $\Theta(n)-\Theta(1)$ 的了,我们把区间最大子段和也优化成了 $\Theta(n)-\Theta(1)$。


总结一下,序列上的问题化归到最后本质上基本都是 $\log$ 分块然后块间二进制瞎搞(个别的递归一层)。树上的问题除了 LCA 拍上链以外别的基本都是用的树分块或者 ART(实际上 UFDS 和反问题也可以这么搞,就是有点阴间)。

更多的问题能不能用类似的套路搞,比如区间 or?或者进一步区间 nand?限于笔者水平,在此不得而知,若读者有所了解,还请不吝赐教;如若文章存在纰漏,也请劳烦指出。

有个暴论,一个正常的 01 序列静态区间查询全都可以这么搞,因为 $\log$ 分块后块内总状态数有限,如果不行就再递归一层。

至此,且容我暂且搁笔。

return20071007 Avatar