线段树(区间修改)

struct Tag {
  void apply(Tag& v) {

  }
};

struct Info {
  void apply(Tag& v) {

  }
  friend Info operator + (Info a, Info b) {
    Info res = a;

    return res;
  }
};

struct SegmentTree {
  vector<Info> info;
  vector<Tag> tag;
  int n;
  SegmentTree() : n(0) { }
  SegmentTree(int n_) {
    n = n_;
    info.assign(4 << __lg(n), Info());
    tag.assign(4 << __lg(n), Tag());
  }
  void build(int p, int l, int r, vector<Info> &v) {
    if (l == r) {
      info[p] = v[l];
      return;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid, v);
    build(p << 1 | 1, mid + 1, r, v);
    push_up(p);
  }
  void apply(int p, Tag &v) {
    info[p].apply(v);
    tag[p].apply(v);
  }
  void push_up(int p) {
    info[p] = info[p << 1] + info[p << 1 | 1];
  }
  void push_down(int p) {
    // if (!tag[p]) return; !!!
    apply(p << 1, tag[p]);
    apply(p << 1 | 1, tag[p]);
    tag[p] = Tag();
  }
  void range_apply(int p, int l, int r, int x, int y, Tag &v) {
    if (l > y || r < x) {
      return;
    }
    if (l >= x && r <= y) {
      apply(p, v);
      return;
    }
    int mid = l + r >> 1;
    push_down(p);
    range_apply(p << 1, l, mid, x, y, v);
    range_apply(p << 1 | 1, mid + 1, r, x, y, v);
    push_up(p);
  }
  void range_apply(int l, int r, Tag &v) {
    return range_apply(1, 1, n, l, r, v);
  }
  void modify(int p, int l, int r, int x, Info& v) {
    if (l == r) {
      info[p] = v;
      return;
    }
    int mid = l + r >> 1;
    if (x <= mid) modify(p << 1, l, mid, x, v);
    else modify(p << 1 | 1, mid + 1, r, x, v);
  }
  void modify(int x, Info& v) {
    modify(1, 1, n, x, v);
  }
  Info range_query(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 mid = l + r >> 1;
    push_down(p);
    Info res = range_query(p << 1, l, mid, x, y) + range_query(p << 1 | 1, mid + 1, r, x, y);
    return res;
  }
  Info range_query(int l, int r) {
    return range_query(1, 1, n, l, r);
  }
};