Segment Tree 模板和例题

模板

这个模板实现的是区间修改的线段树,支持区间加和区间查询. 使用的时候只需要修改 Tag, Info, Node 三个类的实现.

SegmentTree 的构造函数参数 vector 数组下标从 0 开始. SegmentTree 的 vector 成员数组下标从 1 开始.

void change(pos, V val) 单点 set
void add(int pos, V val) 单点加
void modify(int ql, int qr, Tag t) 区间加
Info query(int ql, int qr) 区间查询

之后可以加上线段树上二分的方法.

#ifndef SEGMENT_TREE_H
#define SEGMENT_TREE_H

#include <tuple>
#include <vector>

using namespace std;
using ll = long long;

struct Tag {
  ll val;

  bool empty() const { return val == 0; }
  Tag operator+(const Tag &rh) const {
    Tag res{val + rh.val};
    return res;
  }
  void clear() { val = 0; }
};

struct Info {
  int len;
  ll val;

  Info operator+(const Info &rh) const {
    Info res{len + rh.len, val + rh.val};
    return res;
  }

  Info operator+(const Tag &t) const {
    Info res{len, val + 1LL * len * t.val};
    return res;
  }
};

struct Node {
  Info info;
  Tag tag;

  Node() : info{}, tag{} {}
  Node(ll val) : info{1, val}, tag{0} {}
};

template <typename V> struct SegmentTree {
  int n{0};
  vector<V> a{};

  vector<Node> seg{};

  explicit SegmentTree(vector<V> &a_) {
    n = int(a_.size());
    a = vector<V>(n + 1);
    copy(a_.begin(), a_.end(), a.begin() + 1);
    seg = vector<Node>(n * 4 + 10);
    build(1, 1, n);
  }

  void change(int pos, V val) {
    a[pos] = val;
    change(1, 1, n, pos, val);
  }
  void modify(int ql, int qr, Tag t) { modify(1, 1, n, ql, qr, t); }
  Info query(int ql, int qr) { return query(1, 1, n, ql, qr); }
  void add(int pos, V val) { modify(pos, pos, {val}); }

  static pair<int, int> child(int id) { return {id * 2, id * 2 + 1}; }

  void update(int id) {
    auto [lc, rc] = child(id);
    seg[id].info = seg[lc].info + seg[rc].info;
  }

  void build(int id, int l, int r) {
    if (l == r) {
      seg[id] = Node(a[l]);
      return;
    }

    int mid = (l + r) / 2;
    auto [lc, rc] = child(id);
    build(lc, l, mid);
    build(rc, mid + 1, r);
    update(id);
  }

  void push_down(int id) {
    Tag &t = seg[id].tag;
    if (t.empty())
      return;

    auto [lc, rc] = child(id);
    set_tag(lc, t);
    set_tag(rc, t);
    t.clear();
  }

  void set_tag(int id, Tag t) {
    seg[id].info = seg[id].info + t;
    seg[id].tag = seg[id].tag + t;
  }

  void change(int id, int l, int r, int pos, V val) {
    if (l == r) {
      seg[id] = Node(val);
      return;
    }

    push_down(id);
    int mid = (l + r) / 2;
    auto [lc, rc] = child(id);
    if (pos <= mid)
      change(lc, l, mid, pos, val);
    else
      change(rc, mid + 1, r, pos, val);
    update(id);
  }

  void modify(int id, int l, int r, int ql, int qr, Tag t) {
    if (l >= ql && r <= qr) {
      set_tag(id, t);
      return;
    }
    int mid = (l + r) / 2;
    auto [lc, rc] = child(id);
    push_down(id);
    if (qr <= mid)
      modify(lc, l, mid, ql, qr, t);
    else if (ql > mid)
      modify(rc, mid + 1, r, ql, qr, t);
    else {
      modify(lc, l, mid, ql, mid, t);
      modify(rc, mid + 1, r, mid + 1, qr, t);
    }
    update(id);
  }

  Info query(int id, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) {
      return seg[id].info;
    }
    int mid = (l + r) / 2;
    auto [lc, rc] = child(id);
    push_down(id);
    if (qr <= mid)
      return query(lc, l, mid, ql, qr);
    else if (ql > mid)
      return query(rc, mid + 1, r, ql, qr);
    else
      return query(lc, l, mid, ql, mid) + query(rc, mid + 1, r, mid + 1, qr);
  }
};

#endif

题单1

下面使用这个模板来做洛谷上一些简单的线段树题目. 这个题单来自于洛谷的线段树题单

P1908 逆序对

求数组的逆序对. 先对数组进行离散化, 对离散化之后的值域创建线段树. 对于当前值 x, 求出之前有多少个 $\le x$ 的值, 也就是区间求和. 插入 $x$ 的时候, 我们需要使用单点加. 模板中恰好支持单点加和区间查询.

void solve() {
  int n;
  cin >> n;
  ll ans = 0;
  VI a(n);
  SegmentTree<int> tree(a);

  For(i, 0, n) cin >> a[i];
  VI b(a);
  sort(all(b));
  b.resize(distance(b.begin(), unique(all(b))));
  auto get = [&](int x) -> int {
    return lower_bound(all(b), x) - b.begin() + 1;
  };
  For(i, 0, n) {
    int y = get(a[i]);
    ans += (i - tree.query(1, y).val);
    tree.add(y, 1);
  }

  cout << ans << '\n';
}

P1816 忠诚

这道题目只需要区间查询最小值, 没有任何修改操作. 因此我们只需要对 Info 的加法做修改即可. 涉及到懒标记的部分全部都不用改.

struct Tag {
  ll val;

  bool empty() const { return val == 0; }
  Tag operator+(const Tag& rh) const {
    Tag res{val + rh.val};
    return res;
  }
  void clear() { val = 0; }
};

struct Info {
  int len;
  ll val;

  Info operator+(const Info& rh) const {
    Info res{len + rh.len, min(val, rh.val)};
    return res;
  }

  Info operator+(const Tag& t) const {
    Info res{len, val + 1LL * len * t.val};
    return res;
  }
};

struct Node {
  Info info;
  Tag tag;

  Node() : info{}, tag{} {}
  Node(ll val) : info{1, val}, tag{0} {}
};

void solve() {
  int n, q;
  cin >> n >> q;
  VI a(n);
  for (auto& x : a) cin >> x;
  SegmentTree<int> tree(a);
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << tree.query(l, r).val << ' ';
  }
  cout << '\n';
}

P3372 【模板】线段树 1

上面的模板默认支持区间加和区间求和, 所以不需要对模板做任何修改.

void solve() {
  int n, q;
  cin >> n >> q;
  VL a(n);
  for (auto& x : a) cin >> x;
  SegmentTree<ll> tree(a);
  while (q--) {
    int op, l, r;
    ll k;
    cin >> op >> l >> r;
    if (op == 1) {
      cin >> k;
      tree.modify(l, r, {k});
    } else {
      cout << tree.query(l, r).val << '\n';
    }
  }
}

P3870 [TJOI2009] 开关

我们需要求一个区间内奇数的个数, 区间内的奇偶性是比较好维护的. 我们只需要记录给定区间被翻转的次数的奇偶性.

具体来说, 假设一个区间长度是 len, 区间内奇数的个数是 val, 如果这个区间被翻转了奇数次, 那么奇数个数变成了 len - val. 如果这个区间被翻转了偶数次, 那么奇数个数还是 val. 这就是懒标记需要的操作.

区间合并操作就是简单的加法.

标记合并也非常简单, 只需要记录奇偶性.

struct Tag {
  ll val;

  bool empty() const { return val == 0; }
  Tag operator+(const Tag& rh) const {
    Tag res{(val + rh.val) & 1};
    return res;
  }
  void clear() { val = 0; }
};

struct Info {
  int len;
  ll val;

  Info operator+(const Info& rh) const {
    Info res{len + rh.len, val + rh.val};
    return res;
  }

  Info operator+(const Tag& t) const {
    Info res = *this;
    if (t.val & 1) res.val = len - val;
    return res;
  }
};

struct Node {
  Info info;
  Tag tag;

  Node() : info{}, tag{} {}
  Node(ll val) : info{1, val}, tag{0} {}
};

void solve() {
  int n, q;
  cin >> n >> q;
  VI a(n);
  SegmentTree<int> tree(a);
  while (q--) {
    int op, l, r;
    cin >> op >> l >> r;
    if (op == 0) {
      tree.modify(l, r, {1});
    } else {
      cout << tree.query(l, r).val << '\n';
    }
  }
}

P1438 无聊的数列

在一个区间上加上一个等差数列, 因为等差数列的差分是固定的, 因此我们可以考虑在差分数组操作, 对应在差分数组上进行区间加操作.

对于等差数列中的 K, 可以转化成在差分数组上的两个单点加操作.

对于等差数列的公差 D, 转化成在差分数组的区间 [l + 1, r] 上进行区间加 D. 不要忘了还需要在 r + 1 位置单点减去 (r - l) * D. 因为在差分数组的任何一个位置进行修改都会影响后面的所有位置, 所以我们需要在 r + 1 恢复.

还要注意判断 r + 1 是否在数组范围内.

void solve() {
  int n, q;
  cin >> n >> q;
  VL a(n);
  for (auto& x : a) cin >> x;
  VL b(n);
  b[0] = a[0];
  For(i, 1, n) b[i] = a[i] - a[i - 1];

  SegmentTree<ll> tree(b);
  while (q--) {
    int op, l, r, K, D, p;
    cin >> op;
    if (op == 1) {
      cin >> l >> r >> K >> D;
      tree.add(l, K);
      if (r + 1 <= n) tree.add(r + 1, -1LL * (r - l) * D - K);

      if (l != r) {
        tree.modify(l + 1, r, {D});
      }
    } else {
      cin >> p;
      cout << tree.query(1, p).val << '\n';
    }
  }
}

P1253 扶苏的问题

题目含有区间 set, 此时维护一个一元一次函数的系数比较方便. 对于函数 $ax + b$, 我们在懒标记中维护参数 $a$ 和 $b$.

如果当前系数是 $(a_1, b_1)$, 如果在这个区间上应用一个函数 $(a_2, b_2)$, 此时系数变成 $(a_1 a_2, a_2 b_1 + b_2)$

对于操作 1, 相当于打标记 $(0, x)$

对于操作 2, 相当于打标记 $(1, x)$

注意修改 Tag 的默认构造函数, 应该初始化成有意义的空值 $(1, 0)$.

struct Tag {
  ll a, b;

  bool empty() const { return a == 1 && b == 0; }
  Tag operator+(const Tag& rh) const {
    Tag res{a * rh.a, b * rh.a + rh.b};
    return res;
  }
  void clear() { a = 1, b = 0; }
  Tag() : a(1), b(0) {}
  Tag(ll a_, ll b_) : a(a_), b(b_) {}
};

struct Info {
  int len;
  ll val;

  Info operator+(const Info& rh) const {
    Info res{len + rh.len, max(val, rh.val)};
    return res;
  }

  Info operator+(const Tag& t) const {
    Info res{len, t.a * val + t.b};
    return res;
  }
};

struct Node {
  Info info;
  Tag tag;

  Node() : info{}, tag{} {}
  Node(ll val) : info{1, val}, tag{1, 0} {}
};

void solve() {
  int n, q;
  cin >> n >> q;
  VL a(n);
  for (auto& x : a) cin >> x;
  SegmentTree<ll> tree(a);

  while (q--) {
    int op, l, r, x;
    cin >> op >> l >> r;
    if (op == 1) {
      cin >> x;
      tree.modify(l, r, {0, x});
    } else if (op == 2) {
      cin >> x;
      tree.modify(l, r, {1, x});
    } else {
      cout << tree.query(l, r).val << '\n';
    }
  }
}

P3373 【模板】线段树 2

和上面扶苏的问题一样, 在懒标记中维护一元一次函数的系数 $(a, b)$, 在节点中还需要维护长度.

合并 Info 与 Tag 的时候, 注意要把区间长度 len 考虑进去.

ll M;
struct Tag {
  ll a, b;

  bool empty() const { return a == 1 && b == 0; }
  Tag operator+(const Tag& rh) const {
    Tag res{a * rh.a % M, (rh.a * b % M + rh.b) % M};
    return res;
  }
  void clear() { a = 1, b = 0; }
  Tag() : a(1), b(0) {}
  Tag(ll a_, ll b_) : a(a_), b(b_) {}
};

struct Info {
  int len;
  ll val;

  Info operator+(const Info& rh) const {
    Info res{len + rh.len, (val + rh.val) % M};
    return res;
  }

  Info operator+(const Tag& t) const {
    Info res{len, (t.a * val % M + t.b * len % M) % M};
    return res;
  }
};

struct Node {
  Info info;
  Tag tag;

  Node() : info{}, tag{} {}
  Node(ll val) : info{1, val}, tag{} {}
};

void solve() {
  int n, q;
  cin >> n >> q >> M;

  VL a(n);
  for (auto& x : a) cin >> x;
  SegmentTree tree(a);
  while (q--) {
    int op, l, r, k;
    cin >> op >> l >> r;
    if (op == 1) {
      cin >> k;
      tree.modify(l, r, {k, 0});
    } else if (op == 2) {
      cin >> k;
      tree.modify(l, r, {1, k});
    } else {
      cout << tree.query(l, r).val % M << '\n';
    }
  }
}

P6492 [COCI 2010/2011 #6] STEP

这道题目只需要支持单点修改和区间查询，和 Tag 相关的都不需要做。

关键是处理两个节点的 Info 相加操作：维护前缀合法字串长度、后缀合法字串长度、整个区间最大合法字串长度、当前区间的左端点、当前区间的右端点。

这和求最大子段和的逻辑是完全类似的。

struct Tag {
  ll val;

  bool empty() const { return val == 0; }
  Tag operator+(const Tag& rh) const {
    Tag res{val + rh.val};
    return res;
  }
  void clear() { val = 0; }
};

struct Info {
  int len;
  int pre, suf, val;
  int L, R;

  Info() : len{1}, pre{1}, suf{1}, val{1}, L{0}, R{0} {}
  Info(int len_, int pre_, int suf_, int val_, int L_, int R_)
      : len(len_), pre(pre_), suf(suf_), val(val_), L(L_), R(R_) {}

  Info operator+(const Info& rh) const {
    Info res{len + rh.len, pre, rh.suf, max(val, rh.val), L, rh.R};

    if (R != rh.L) {
      ckmax(res.val, suf + rh.pre);
      if (pre == len) res.pre += rh.pre;
      if (rh.suf == rh.len) res.suf += suf;
    }

    return res;
  }

  Info operator+(const Tag&) const {
    Info res{*this};
    return res;
  }
};

struct Node {
  Info info;
  Tag tag;

  Node() : info{}, tag{} {}
  Node(int val) : info{1, 1, 1, 1, val, val}, tag{0} {}
};

void solve() {
  int n, q;
  cin >> n >> q;
  VI a(n);
  SegmentTree<int> tree(a);

  while (q--) {
    int pos;
    cin >> pos;
    if (tree.a[pos] == 0) {
      tree.change(pos, 1);
    } else {
      tree.change(pos, 0);
    }
    cout << tree.query(1, n).val << '\n';
  }
}

P1637 三元上升子序列

这道题目只需要区间查询。对于 $a_i$ 找到位置 $i$ 前面有多少个 $< a_i$ 的数字，还需要找到位置 $i$ 后面有多少个 $> a_i$ 的数字。这可以使用两棵线段树分别求。

对数组进行离散化，在值域上建立线段树，做法和求逆序对完全类似。

给定数组的值域比较小，离散化可能是不必要的。

void solve() {
  int n;
  cin >> n;
  ll ans{};
  VI a(n);
  for (auto& x : a) cin >> x;

  VI b(a);
  sort(all(b));
  b.resize(distance(b.begin(), unique(all(b))));
  auto get = [&](int x) -> int {
    return distance(b.begin(), lower_bound(all(b), x)) + 1;
  };

  int sz = SZ(b);
  VI b1(sz), la(n), ra(n);
  SegmentTree tree1(b1), tree2(b1);
  For(i, 0, n) {
    int x = a[i], y = get(x);
    if (y >= 2) la[i] = tree1.query(1, y - 1).val;
    tree1.add(y, 1);
  }
  Rof(i, 0, n) {
    int x = a[i], y = get(x);
    ra[i] = n - 1 - i - tree2.query(1, y).val;
    tree2.add(y, 1);
  }

  For(i, 0, n) { ans += 1LL * la[i] * ra[i]; }
  cout << ans << '\n';
}

P1558 色板游戏

这道题目就有一点意思了，关键在于内存限制是 128MB。

因为颜色数量比较少，我们可以对每一种颜色使用单独的一棵线段树维护在给定的区间是否存在这种颜色。

对于区间 Set 操作，最无脑的办法是使用之前熟悉的维护一元一次函数系数的方法。但是这道题目的内存限制比较小，使用这种方法会直接 MLE，因此我们不能在节点中维护太多的信息。

这道题目的区间 Set 操作比较特殊，其实只有两种可能，一种是权值为 1, 一种是权值是 0。同时，我们还需要表示 Tag 是空的情况，因此我们只需要使用 short 类型即可。

对于 Info 结构体，只需要表示这个区间内是否含有至少一个 1，使用一个单独的 bool 即可。这样 Node 结构体的大小只有 4 个字节。完全可以接受。

事实上，在 SegmentTree 里面，我们还存储了一个数组 a，不过大小为 $10^5$ 的 vector<int> 只有 0.4MB 左右， 30 个数组也只有 12MB，在这道题目里面不是关键。

struct Tag {
  short a;

  Tag() : a(-1) {}
  Tag(int a_) : a(a_) {}
  bool empty() const { return a == -1; }
  Tag operator+(const Tag& rh) const { return rh; }
  void clear() { a = -1; }
};

struct Info {
  bool val;

  Info operator+(const Info& rh) const {
    Info res{val || rh.val};
    return res;
  }

  Info operator+(const Tag& t) const {
    Info res = *this;
    if (t.a == 0)
      res.val = false;
    else if (t.a == 1)
      res.val = true;
    return res;
  }

  Info() : val(false) {}
  Info(bool val_) : val(val_) {}
};

struct Node {
  Info info;
  Tag tag;

  Node() : info{}, tag{} {}
  Node(bool val) : info{val}, tag{} {}
};

void solve() {
  int n, T, q;
  cin >> n >> T >> q;

  vector<SegmentTree<int>> trees(30);
  For(i, 0, T) {
    VI a(n);
    trees[i] = SegmentTree<int>(a);
  }
  trees[0].modify(1, n, {1});

  while (q--) {
    string op;
    int l, r, C;
    cin >> op >> l >> r;
    if (l > r) swap(l, r);

    if (op == "C") {
      cin >> C;
      For(i, 0, T) {
        if (i + 1 == C) {
          trees[i].modify(l, r, {1});
        } else {
          trees[i].modify(l, r, {0});
        }
      }
    } else {
      int ans{};
      For(i, 0, T) { ans += trees[i].query(l, r).val; }
      cout << ans << '\n';
    }
  }
}

P4513 小白逛公园

这道题需要求最经典的最大子段和，需要支持单点修改。

因此我们不需要对 Tag 相关的做修改，因为不会用到懒标记。最大子段和的逻辑都在 Info 结构体的合并操作中进行。

前缀有两种情况：左孩子的前缀，左孩子的总和+右孩子的前缀
后缀有两种情况：右孩子的后缀，右孩子的总和+左孩子的后缀
最大子段和有三种情况：左孩子的最大子段和，右孩子的最大子段和，左孩子的后缀+右孩子的前缀

struct Tag {
  ll val;

  bool empty() const { return val == 0; }
  Tag operator+(const Tag& rh) const {
    Tag res{val + rh.val};
    return res;
  }
  void clear() { val = 0; }
};

struct Info {
  int len;
  int pre, suf, val, sum;

  Info operator+(const Info& rh) const {
    Info res{len + rh.len, max(pre, sum + rh.pre), max(rh.suf, rh.sum + suf),
             max({val, rh.val, suf + rh.pre}), sum + rh.sum};

    return res;
  }

  Info operator+(const Tag&) const { return *this; }
};

struct Node {
  Info info;
  Tag tag;

  Node() : info{}, tag{} {}
  Node(int val) : info{1, val, val, val, val}, tag{0} {}
};

void solve() {
  int n, q;
  cin >> n >> q;
  VI a(n);
  for (auto& x : a) cin >> x;
  SegmentTree<int> tree(a);
  while (q--) {
    int op, l, r, p, s;
    cin >> op;
    if (op == 1) {
      cin >> l >> r;
      if (l > r) swap(l, r);
      cout << tree.query(l, r).val << '\n';
    } else {
      cin >> p >> s;
      tree.change(p, s);
    }
  }
}

P4145 上帝造题的七分钟 2 / 花神游历各国

这道题目需要支持区间开平方操作，这个操作没有比较好的处理办法：我们无法根据开平方的次数，快速计算出当前区间的开平方之后的区间和。

注意到数据范围只有 $2^{64}$, 对于一个整数，开平方的次数最多只有 7 次，变成 1 之后就不会改变了。也就是说如果一个区间内全部是 1, 那么对这个区间进行开平方操作是无效操作。

因此我们只需要修改区间修改 modify 方法，如果当前节点对应的区间元素全部是 1, 那么直接返回。如果当前节点是叶子节点，此时我们才需要进行开平方操作。

新增的 bool Info::full() 方法表示当前节点对应的区间中，所有元素是否全部都是 1. 我的判定方法是求出当前区间的元素和，如果恰好等于区间长度，说明区间内每个元素都是 1.

struct Tag {
  int val;

  bool empty() const { return val == 0; }
  Tag operator+(const Tag& rh) const {
    Tag res{val + rh.val};
    return res;
  }
  void clear() { val = 0; }
};

struct Info {
  int len;
  ll val;

  Info operator+(const Info& rh) const {
    Info res{len + rh.len, val + rh.val};
    return res;
  }

  Info operator+(const Tag& t) const {
    Info res{*this};
    if (len == 1) {
      For(i, 0, t.val) {
        res.val = sqrt(res.val);
        if (res.val == 1) break;
      }
    }
    return res;
  }

  bool full() const { return len == val; }
};

struct Node {
  Info info;
  Tag tag;

  Node() : info{}, tag{} {}
  Node(ll val) : info{1, val}, tag{0} {}
};

void SegmentTree::modify(int id, int l, int r, int ql, int qr, Tag t) {
  if (l >= ql && r <= qr) {
    if (seg[id].info.full())
      return;
    else if (l == r) {
      set_tag(id, t);
      return;
    }
  }

  int mid = (l + r) / 2;
  auto [lc, rc] = child(id);
  push_down(id);
  if (qr <= mid)
    modify(lc, l, mid, ql, qr, t);
  else if (ql > mid)
    modify(rc, mid + 1, r, ql, qr, t);
  else {
    modify(lc, l, mid, ql, mid, t);
    modify(rc, mid + 1, r, mid + 1, qr, t);
  }
  update(id);
}

void solve() {
  int n, q;
  cin >> n;
  VL a(n);
  cin >> a;
  cin >> q;
  SegmentTree<ll> tree(a);
  while (q--) {
    int op, l, r;
    cin >> op >> l >> r;
    if (l > r) swap(l, r);
    if (op == 0) {
      tree.modify(l, r, {1});
    } else {
      cout << tree.query(l, r).val << '\n';
    }
  }
}

题单2

来自于 CP Algorithms

CF339D. Xenia and Bit Operations

这道题目只需要单点修改。

我们需要在 Info 中额外记录层数信息，叶子节点的层数是 1, 依次网上递增。在偶数层，我们使用 OR 操作，在奇数层我们使用 XOR 操作，这恰好对应 Info 的加法运算符。

struct Tag {
  ll val;

  bool empty() const { return val == 0; }
  Tag operator+(const Tag& rh) const {
    Tag res{val + rh.val};
    return res;
  }
  void clear() { val = 0; }
};

struct Info {
  int val;
  int level;

  Info operator+(const Info& rh) const {
    Info res{0, max(level, rh.level) + 1};
    if (res.level & 1)
      res.val = val ^ rh.val;
    else
      res.val = val | rh.val;
    return res;
  }

  Info operator+(const Tag&) const { return *this; }
};

struct Node {
  Info info;
  Tag tag;

  Node() : info{0, 1}, tag{} {}
  Node(int val, int level = 1) : info{val, level}, tag{0} {}
};

void solve() {
  int n, m;
  cin >> n >> m;
  VI a(1 << n);
  For(i, 0, (1 << n)) cin >> a[i];
  SegmentTree<int> tree(a);
  while (m--) {
    int pos, b;
    cin >> pos >> b;
    tree.change(pos, b);
    cout << tree.query(1, 1 << n).val << '\n';
  }
}

UVA 11402 - Ahoy, Pirates!

这道题目要求对 01 数组进行区间翻转和区间 Set，以前我会使用维护一元一次函数参数的方式来做区间 Set。在这道题目里面我只使用了 Tag 里面的两个 Int 来实现。

如何合并两个 Tag：

如果 rh 是 Set 操作，那么结果就是 rh
如果 rh 是翻转操作，此时我们需要考虑当前 Tag
- 如果当前 Tag 是 Set 操作，那么我们需要把 Set 的值翻转
- 如果当前 Tag 是翻转操作，那么我们只需要叠加翻转次数，保留奇偶性

如何把 Tag 打到 Info 上：

如果是翻转操作，只需要使用 len - val
如果是 Set 操作，根据要 Set 的值来得到答案

struct Tag {
  int val, inv;

  bool empty() const { return val == -1 && inv == 0; }
  Tag operator+(const Tag& rh) const {
    Tag res{*this};
    if (rh.val != -1)
      res = rh;
    else {
      if (res.val != -1)
        res.val = 1 - res.val;
      else {
        res.inv = (res.inv + rh.inv) & 1;
      }
    }
    return res;
  }
  void clear() { val = -1, inv = 0; }
  Tag() : val(-1), inv(0) {}
  Tag(int val_, int inv_) : val(val_), inv(inv_) {}
};

struct Info {
  int len;
  int val;

  Info operator+(const Info& rh) const {
    Info res{len + rh.len, val + rh.val};
    return res;
  }

  Info operator+(const Tag& t) const {
    Info res{*this};
    if (t.inv) res.val = len - val;
    if (t.val != -1) {
      if (t.val == 0)
        res.val = 0;
      else
        res.val = len;
    }
    return res;
  }
};

struct Node {
  Info info;
  Tag tag;

  Node() : info{}, tag{} {}
  Node(int val) : info{1, val}, tag{} {}
};

void solve() {
  int M;
  cin >> M;
  string s;
  while (M--) {
    int T;
    string t, tmp;
    cin >> T >> t;
    while (T--) tmp += t;
    s += tmp;
  }
  int n = SZ(s);
  vector<int> a(n);
  For(i, 0, n) a[i] = s[i] == '1';
  SegmentTree<int> tree(a);
  int q, idx = 1;
  cin >> q;
  For1(i, 1, q) {
    string op;
    int l, r;
    cin >> op >> l >> r;
    l++, r++;
    if (op == "F") {
      tree.modify(l, r, {1, 0});
    } else if (op == "E") {
      tree.modify(l, r, {0, 0});
    } else if (op == "I") {
      tree.modify(l, r, {-1, 1});
    } else if (op == "S") {
      cout << "Q" << idx++ << ": " << tree.query(l, r).val << '\n';
    }
  }
}

SPOJ - GSS3

这道题和上面的洛谷 P4513 是一样的。

Codeforces - Distinct Characters Queries

这道题目只需要在每个节点维护每个字符出现次数。只需要单点修改。

struct Info {
  VI cnt;

  Info() : cnt{VI(26)} {}
  Info(int id) : cnt{VI(26)} { ++cnt[id]; }

  Info operator+(const Info& rh) const {
    Info res{};
    For(i, 0, 26) res.cnt[i] = cnt[i] + rh.cnt[i];
    return res;
  }

  Info operator+(const Tag&) const { return *this; }
  int get_val() const {
    int res{};
    for (auto i : cnt) res += i > 0;
    return res;
  }
};

void solve() {
  string s;
  cin >> s;
  int n{SZ(s)};
  VI a(n);
  For(i, 0, n) a[i] = s[i] - 'a';
  SegmentTree<int> tree(a);
  int q;
  cin >> q;
  while (q--) {
    int op, l, r, pos;
    string ch;
    cin >> op;
    if (op == 1) {
      cin >> pos >> ch;
      int id = ch[0] - 'a';
      tree.change(pos, id);
    } else {
      cin >> l >> r;
      cout << tree.query(l, r).get_val() << '\n';
    }
  }
}

Codeforces - Knight Tournament

这道题目如果使用线段树做思路还挺有趣的。

我们需要做区间 Set 操作，不过要求是这样的，对于一个区间，只有第一次 Set 的 Tag 有效，随后进行的 Set 操作无效。

我的做法是这样的：push_down 下推 Tag 的时候，不清空当前节点的 Tag。对节点打标记 set_tag 的时候，先合并标记，然后把合并后的标记和节点的 Info 相加。因此我们需要对这两个成员函数做一些小修改。

这就能够满足题目要求。

struct Tag {
  ll val;

  Tag() : val(0) {}
  Tag(ll val_) : val(val_) {}

  bool empty() const { return val == 0; }
  Tag operator+(const Tag& rh) const {
    if (val) return *this;
    return rh;
  }
  void clear() { val = 0; }
};

struct Info {
  int len;
  ll val;

  Info() : len(1), val(0) {}
  Info(int len_, ll val_) : len(len_), val(val_) {}

  Info operator+(const Info&) const { return *this; }

  Info operator+(const Tag& t) const {
    Info res{len, t.val};
    return res;
  }
};

struct Node {
  Info info;
  Tag tag;

  Node() : info{}, tag{} {}
  Node(ll val) : info{1, val}, tag{0} {}
};

void SegmentTree::push_down(int id) {
  Tag& t = seg[id].tag;
  if (t.empty()) return;

  auto [lc, rc] = child(id);
  set_tag(lc, t);
  set_tag(rc, t);
  // t.clear();
}

void SegmentTree::set_tag(int id, Tag t) {
  seg[id].tag = seg[id].tag + t;
  seg[id].info = seg[id].info + seg[id].tag;
}

void solve() {
  int n, q;
  cin >> n >> q;
  VI a(n);
  SegmentTree tree(a);
  while (q--) {
    int l, r, p;
    cin >> l >> r >> p;

    if (l <= p - 1) {
      tree.modify(l, p - 1, {p});
    }
    if (p + 1 <= r) {
      tree.modify(p + 1, r, {p});
    }
  }
  For1(i, 1, n) { cout << tree.query(i, i).val << ' '; }
  cout << '\n';
}

有趣的题

HDU 5649. DZY Loves Sorting

这道题目挺有趣的。

首先考虑二分答案（怎么想到的呢？）

设 $a_k = x$，如果经过 $m$ 次操作之后，位置 $k$ 的值 $< x$，说明我们二分的 $x$ 偏大了。如果位置经过所有操作之后，位置 $k$ 的值 $\ge x$，说明答案一定 $\ge x$，我们需要找到满足这个条件的最大的 $x$。这就是我们的 check 函数。

也就是 check 函数中我们只需要判定位置 $k$ 是否 $\ge x$。我们可以把原来的数组转化成二进制数组，如果 $a_i \ge x$，那么设置为 1, 否则设置成 0.

对一个二进制数组排序非常简单，如果是升序，首先数出这个区间内有多少个 1, 然后做区间 Set。逆序排序也是类似的。

二分的复杂度是 $log(n)$，判定的复杂度是 $n + m log(n)$

模板里面，涉及区间 Set 操作的时候，需要注意 Tag 结构体的初始化，因为我们需要区分什么时候标记是空的。

struct Tag {
  int val;

  bool empty() const { return val == -1; }
  Tag operator+(const Tag& rh) const { return rh; }
  void clear() { val = -1; }
  Tag() : val(-1) {}
  Tag(int val_) : val(val_) {}
};

struct Info {
  int len;
  int val;

  Info operator+(const Info& rh) const {
    Info res{len + rh.len, val + rh.val};
    return res;
  }

  Info operator+(const Tag& t) const {
    Info res{len, len * t.val};
    return res;
  }
};

struct Node {
  Info info;
  Tag tag;

  Node() : info{}, tag{} {}
  Node(int val) : info{1, val}, tag{} {}
};

void solve() {
  int n, q;
  cin >> n >> q;
  VI a(n);
  for (auto& x : a) cin >> x;

  struct Ops {
    int op, l, r;
  };
  vector<Ops> ops(q);
  For(i, 0, q) { cin >> ops[i].op >> ops[i].l >> ops[i].r; }
  int k;
  cin >> k;

  auto check = [&](int val) -> bool {
    VI a1(n);
    For(i, 0, n) { a1[i] = (a[i] >= val); }
    SegmentTree<int> tree(a1);
    for (auto [op, l, r] : ops) {
      int cnt = tree.query(l, r).val, len = r - l + 1;
      if (len == cnt || cnt == 0) continue;

      if (op == 0) {
        tree.modify(l, r - cnt, {0});
        tree.modify(r - cnt + 1, r, {1});
      } else {
        tree.modify(l, l + cnt - 1, {1});
        tree.modify(l + cnt, r, {0});
      }
    }
    return tree.query(k, k).val >= 1;
  };

  int l = 1, r = n, mid;
  while (l < r) {
    mid = (l + r + 1) / 2;
    if (check(mid))
      l = mid;
    else
      r = mid - 1;
  }
  cout << l << '\n';
}

模板#

题单1#

题单2#

有趣的题#

模板

题单1

题单2

有趣的题