题解 | 区间取反与区间数一

遇到区间问题，考虑双指针，前缀和，树状数组，线段树等算法或数据结构。而本题使用懒标记线段树可以轻松维护所需信息。

jiangly老师的懒标记线段树的模板（我删去了一些此处用不到的功能）：

/*
 *此懒标记线段树是0-base的，用于构造的init_数组也是0-base的
 *区间查询和区间修改的区间[l,r)皆为左闭右开，也为0-base
*/
template<class Info, class Tag>
struct LazySegmentTree {
  int n;
  std::vector<Info> info;
  std::vector<Tag> tag;
  LazySegmentTree() : n(0) {}
  LazySegmentTree(int n_, Info v_ = Info()) {
    init(n_, v_);
  }
  template<class T>
  LazySegmentTree(std::vector<T> init_) {
    init(init_);
  }
  void init(int n_, Info v_ = Info()) {
    init(std::vector(n_, v_));
  }
  template<class T>
  void init(std::vector<T> init_) {
    n = init_.size();
    info.assign(4 << std::__lg(n), Info());
    tag.assign(4 << std::__lg(n), Tag());
    std::function<void(int, int, int)> build = [&](int p, int l, int r) {
      if (r - l == 1) {
        info[p] = init_[l];
        return;
      }
      int m = (l + r) / 2;
      build(2 * p, l, m);
      build(2 * p + 1, m, r);
      pull(p);
    };
    build(1, 0, n);
  }
  void pull(int p) {
    info[p] = info[2 * p] + info[2 * p + 1];
  }
  void apply(int p, const Tag& v) {
    info[p].apply(v);
    tag[p].apply(v);
  }
  void push(int p) {
    apply(2 * p, tag[p]);
    apply(2 * p + 1, tag[p]);
    tag[p] = Tag();
  }
  void modify(int p, int l, int r, int x, const Info& v) {
    if (r - l == 1) {
      info[p] = v;
      return;
    }
    int m = (l + r) / 2;
    push(p);
    if (x < m) {
      modify(2 * p, l, m, x, v);
    } else {
      modify(2 * p + 1, m, r, x, v);
    }
    pull(p);
  }
  void modify(int p, const Info& v) {
    modify(1, 0, n, p, v);
  }
  Info rangeQuery(int p, int l, int r, int x, int y) {
    if (l >= y || r <= x) {
      return Info();
    }
    if (l >= x && r <= y) {
      return info[p];
    }
    int m = (l + r) / 2;
    push(p);
    return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
  }
  Info rangeQuery(int l, int r) {
    return rangeQuery(1, 0, n, l, r);
  }
  void rangeApply(int p, int l, int r, int x, int y, const Tag& v) {
    if (l >= y || r <= x) {
      return;
    }
    if (l >= x && r <= y) {
      apply(p, v);
      return;
    }
    int m = (l + r) / 2;
    push(p);
    rangeApply(2 * p, l, m, x, y, v);
    rangeApply(2 * p + 1, m, r, x, y, v);
    pull(p);
  }
  void rangeApply(int l, int r, const Tag& v) {
    return rangeApply(1, 0, n, l, r, v);
  }
};

struct Tag {
  
  void apply(const Tag& t)& {

  }
};

struct Info {
  
  void apply(const Tag& t)& {

  }
};

Info operator+(const Info& a, const Info& b) {
  return {};
}

需要我们实现的是两个结构体和内部的apply函数以及一个重载运算符。

我们可以发现：记一个区间[l,r]中字符'1'的数量为cnt，那么可以推出字符'0'的数量为r-l+1-cnt，而区间取反后的字符'1'的数量就是取反前字符'0'的数量。

因此对于结构体Info来说，我们需要维护当前区间的字符'1'的个数cnt，由于该模板不存储左右端点，因此我们需要额外存储一个区间长度len。再考虑一下懒标记结构体Tag，设置一个逻辑标志位flip表示当前是否需要对区间进行取反。如果有flip为true的懒标记要下放，那么子节点的懒标记应该对自身的flip进行取反。再考虑Info的apply函数，如果当前懒标记的flip为true，那么表示当前区间字符'1'的数量需要修改为原来字符'0'的数量，具体来说就是cnt = len-cnt。最后考虑'+'的重载，两个区间合并实际上就是两个区间的字符'1'数量cnt相加，两个区间的区间长度len也相加。

构造初始化数组init，就是构造区间长度为1的情况，如果字符串当前字符为'1'，那么cnt就置为1，否则置为0，区间长度len都置为1。

当然注意模板中的区间[l,r)都是左闭右开的，读入的时候需要将左端点l减一，且下标都是从0开始。

#include <iostream>
#include <vector>
#include <functional>
#include <string>

template<class Info, class Tag>
struct LazySegmentTree {
  int n;
  std::vector<Info> info;
  std::vector<Tag> tag;
  LazySegmentTree() : n(0) {}
  LazySegmentTree(int n_, Info v_ = Info()) {
    init(n_, v_);
  }
  template<class T>
  LazySegmentTree(std::vector<T> init_) {
    init(init_);
  }
  void init(int n_, Info v_ = Info()) {
    init(std::vector(n_, v_));
  }
  template<class T>
  void init(std::vector<T> init_) {
    n = init_.size();
    info.assign(4 << std::__lg(n), Info());
    tag.assign(4 << std::__lg(n), Tag());
    std::function<void(int, int, int)> build = [&](int p, int l, int r) {
      if (r - l == 1) {
        info[p] = init_[l];
        return;
      }
      int m = (l + r) / 2;
      build(2 * p, l, m);
      build(2 * p + 1, m, r);
      pull(p);
    };
    build(1, 0, n);
  }
  void pull(int p) {
    info[p] = info[2 * p] + info[2 * p + 1];
  }
  void apply(int p, const Tag& v) {
    info[p].apply(v);
    tag[p].apply(v);
  }
  void push(int p) {
    apply(2 * p, tag[p]);
    apply(2 * p + 1, tag[p]);
    tag[p] = Tag();
  }
  void modify(int p, int l, int r, int x, const Info& v) {
    if (r - l == 1) {
      info[p] = v;
      return;
    }
    int m = (l + r) / 2;
    push(p);
    if (x < m) {
      modify(2 * p, l, m, x, v);
    } else {
      modify(2 * p + 1, m, r, x, v);
    }
    pull(p);
  }
  void modify(int p, const Info& v) {
    modify(1, 0, n, p, v);
  }
  Info rangeQuery(int p, int l, int r, int x, int y) {
    if (l >= y || r <= x) {
      return Info();
    }
    if (l >= x && r <= y) {
      return info[p];
    }
    int m = (l + r) / 2;
    push(p);
    return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
  }
  Info rangeQuery(int l, int r) {
    return rangeQuery(1, 0, n, l, r);
  }
  void rangeApply(int p, int l, int r, int x, int y, const Tag& v) {
    if (l >= y || r <= x) {
      return;
    }
    if (l >= x && r <= y) {
      apply(p, v);
      return;
    }
    int m = (l + r) / 2;
    push(p);
    rangeApply(2 * p, l, m, x, y, v);
    rangeApply(2 * p + 1, m, r, x, y, v);
    pull(p);
  }
  void rangeApply(int l, int r, const Tag& v) {
    return rangeApply(1, 0, n, l, r, v);
  }
};

struct Tag {
  bool flip = false;
  void apply(const Tag& t)& {
    if(t.flip){
      flip = !flip;
    }
  }
};

struct Info {
  int cnt = 0,len = 1;
  void apply(const Tag& t)& {
    if(t.flip){
      cnt = len-cnt;
    }
  }
};

Info operator+(const Info& a, const Info& b) {
  return {a.cnt+b.cnt,a.len+b.len};
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n, q;
  std::cin >> n >> q;

  std::string s;
  std::cin >> s;

  std::vector<Info> init(n);
  for(int i = 0; i < s.size(); i++){
    if(s[i] == '1'){
      init[i].cnt = 1;
    }else{
      init[i].cnt = 0;
    }
    init[i].len = 1;
  }

  LazySegmentTree<Info,Tag> lsgt(init);

  for (int qi = 0; qi < q; qi++) {
    int op, l, r;
    std::cin >> op >> l >> r;
    l--;

    if (op == 1) {
      lsgt.rangeApply(l,r,Tag{true});
    } else {
      std::cout << lsgt.rangeQuery(l,r).cnt << "\n";
    }
  }
}