数据结构：线段树

Posted on 2024-04-29 Edited on 2024-09-12 In 数据结构

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

数据结构：树状数组续

Posted on 2024-04-19 Edited on 2024-09-07 In 数据结构

由于树状数组内容较多，因此分为两篇博客介绍。

本篇博客在上一篇的基础上，介绍二维树状数组、权值树状数组等数据结构以及树状数组的维护和技巧。

数据结构：树状数组

Posted on 2024-04-17 Edited on 2024-09-07 In 数据结构

树状数组是一种支持 单点修改 和 区间查询 的，代码量小的数据结构。

什么是「单点修改」和「区间查询」？

假设有这样一道题：

已知一个数列，你需要进行下面两种操作：

给定，将自增。

给定，求解的和。

其中第一种操作就是「单点修改」，第二种操作就是「区间查询」。

类似地，还有：「区间修改」、「单点查询」。它们分别的一个例子如下：

区间修改：给定，将中的每个数都分别自增；

单点查询：给定，求解的值。

注意到，区间问题一般严格强于单点问题，因为对单点的操作相当于对一个长度为的区间操作。

普通树状数组维护的信息及运算要满足 结合律 且 可差分，如加法（和）、乘法（积）、异或等。

结合律：，其中是一个二元运算符。
可差分：具有逆运算的运算，即已知和可以求出。

需要注意的是：

模意义下的乘法若要可差分，需保证每个数都存在逆元（模数为质数时一定存在）；
例如，这些信息不可差分，所以不能用普通树状数组处理，但是：
- 使用两个树状数组可以用于处理区间最值，见 Efficient Range Minimum Queries using Binary Indexed Trees。
- 本页面也会介绍一种支持不可差分信息查询的，时间复杂度的拓展树状数组。

事实上，树状数组能解决的问题是线段树能解决的问题的子集：树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。然而，树状数组的代码要远比线段树短，时间效率常数也更小，因此仍有学习价值。

有时，在差分数组和辅助数组的帮助下，树状数组还可解决更强的 区间加单点值 和 区间加区间和 问题。

数据结构：ST表

Posted on 2024-04-13 Edited on 2024-09-07 In 数据结构

ST 表（Sparse Table，稀疏表）是用于解决 可重复贡献问题 的数据结构。

什么是可重复贡献问题？

可重复贡献问题 是指对于运算，满足，则对应的区间询问就是一个可重复贡献问题。例如，最大值有，gcd 有，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次，这是我们所不愿意看到的。另外，还必须满足结合律才能使用 ST 表求解。

什么是 RMQ？

RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。解决 RMQ 问题有很多种方法

数据结构：单调队列

Posted on 2024-04-07 Edited on 2024-09-07 In 数据结构

在学习单调队列前，让我们先来看一道例题。

POJ2823 Sliding Window

本题大意是给出一个长度为的数组，编程输出每个连续的数中的最大值和最小值。

最暴力的想法很简单，对于每一段的序列，逐个比较来找出最大值（和最小值），时间复杂度约为。

很显然，这其中进行了大量重复工作，除了开头个和结尾个数之外，每个数都进行了次比较，而题中的数据为，当稍大的情况下，显然会 TLE。

这时所用到的就是单调队列了。

数据结构：单调栈

Posted on 2024-04-02 Edited on 2024-09-07 In 数据结构

何为单调栈？顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。

为了描述方便，以下举例及伪代码以维护一个整数的单调递增栈为例。

数据结构：Sqrt Tree

Posted on 2024-03-27 Edited on 2024-09-07 In 数据结构

给你一个长度为 n 的序列，再给你一个满足结合律的运算（比如均满足结合律），然后对于每一次区间询问，我们需要计算。

Sqrt Tree 可以在的时间内预处理，并在的时间内回答询问。

数据结构：树分块

Posted on 2024-03-21 Edited on 2024-09-07 In 数据结构

树分块的方式

可以参考 ouuan 的博客/莫队、带修莫队、树上莫队详解/树上莫队。

树上莫队同样可以参考文章。

树分块的应用

树分块除了应用于莫队，还可以灵活地运用到某些树上问题中。但可以用树分块解决的题目往往都有更优秀的做法，所以相关的题目较少。

顺带提一句，「gty 的妹子树」的树分块做法可以被菊花图卡掉。

BZOJ4763 雪辉

先进行树分块，然后对每个块的关键点，预处理出它到祖先中每个关键点的路径上颜色的 bitset，以及每个关键点的最近关键点祖先，复杂度是，其中是暴力从每个关键点向上跳的复杂度，是把个 bitset 存下来的复杂度。

回答询问的时候，先从路径的端点暴力跳到所在块的关键点，再从所在块的关键点一块一块地向上跳，直到所在块，然后再暴力跳到。关键点之间的 bitset 已经预处理了，剩下的在暴力跳的过程中计算。单次询问复杂度是，其中是块内暴力跳以及块直接向上跳的复杂度，是将预处理的结果与暴力跳的结果合并的复杂度。数颜色个数可以用 bitset 的 count()，求可以用 bitset 的 _Find_first()。

所以，总复杂度为。

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <iostream>

using namespace std;

int read() {
  int out = 0;
  char c;
  while (!isdigit(c = getchar()));
  for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
  return out;
}

const int N = 100010;
const int B = 666;
const int C = 30000;

void add(int u, int v);
void dfs(int u);

int head[N], nxt[N << 1], to[N << 1], cnt;
int n, m, type, c[N], fa[N], dep[N], sta[N], top, tot, bl[N], key[N / B + 5],
    p[N], keyid[N];
bool vis[N];
bitset<C> bs[N / B + 5][N / B + 5], temp;

int main() {
  int i, u, v, x, y, k, lastans = 0;

  n = read();
  m = read();
  type = read();

  for (i = 1; i <= n; ++i) c[i] = read();

  for (i = 1; i < n; ++i) {
    u = read();
    v = read();
    add(u, v);
    add(v, u);
  }

  dfs(1);

  if (!tot) ++tot;
  if (keyid[key[tot]] == tot) keyid[key[tot]] = 0;
  key[tot] = 1;
  keyid[1] = tot;
  while (top) bl[sta[top--]] = tot;

  for (i = 1; i <= tot; ++i) {  // 预处理
    if (vis[key[i]]) continue;
    vis[key[i]] = true;
    temp.reset();
    for (u = key[i]; u; u = fa[u]) {
      temp[c[u]] = 1;
      if (keyid[u]) {
        if (!p[key[i]] && u != key[i]) p[key[i]] = u;
        bs[keyid[key[i]]][keyid[u]] = temp;
      }
    }
  }

  while (m--) {
    k = read();
    temp.reset();
    while (k--) {
      u = x = read() ^ lastans;
      v = y = read() ^ lastans;

      while (key[bl[x]] != key[bl[y]]) {
        if (dep[key[bl[x]]] > dep[key[bl[y]]]) {
          if (x == u) {  // 若是第一次跳先暴力跳到关键点
            while (x != key[bl[u]]) {
              temp[c[x]] = 1;
              x = fa[x];
            }
          } else
            x = p[x];  // 否则跳一整块
        } else {
          if (y == v) {
            while (y != key[bl[v]]) {
              temp[c[y]] = 1;
              y = fa[y];
            }
          } else
            y = p[y];
        }
      }

      if (keyid[x]) temp |= bs[keyid[key[bl[u]]]][keyid[x]];
      if (keyid[y]) temp |= bs[keyid[key[bl[v]]]][keyid[y]];

      while (x != y) {
        if (dep[x] > dep[y]) {
          temp[c[x]] = 1;
          x = fa[x];
        } else {
          temp[c[y]] = 1;
          y = fa[y];
        }
      }
      temp[c[x]] = true;
    }
    int ans1 = temp.count(), ans2 = (~temp)._Find_first();
    printf("%d %d\n", ans1, ans2);
    lastans = (ans1 + ans2) * type;
  }

  return 0;
}

void dfs(int u) {  // 根据题意找点
  int i, v, t = top;
  for (i = head[u]; i; i = nxt[i]) {
    v = to[i];
    if (v == fa[u]) continue;
    fa[v] = u;
    dep[v] = dep[u] + 1;
    dfs(v);
    if (top - t >= B) {
      key[++tot] = u;
      if (!keyid[u]) keyid[u] = tot;
      while (top > t) bl[sta[top--]] = tot;
    }
  }
  sta[++top] = u;
}

void add(int u, int v) {
  nxt[++cnt] = head[u];
  head[u] = cnt;
  to[cnt] = v;
}