线段树的优雅写法

可以将 Tag 和 Info 用结构体封装，重载运算符 Tag + Tag（标记合并），Info + Info（信息合并），Info += Tag（打标记），这样就可以使用更优雅的方法写线段树了。

例子：P2572

#include <iostream>

using namespace std;

const int kN = 1e5 + 1;

struct T {
  int ta;
  bool tr;

  T(int _ta = -1, bool _tr = 0) : ta(_ta), tr(_tr) {}
  const T &operator+=(const T &o) {
    if (~o.ta) {
      ta = o.ta, tr = 0;
    }
    tr ^= o.tr;
    return *this;
  }
};
struct I {
  int c[2], l[2], r[2], m[2];
  int _l, _r;

  I() {
    for (int i = 0; i < 2; ++i) {
      c[i] = l[i] = r[i] = m[i] = 0;
    }
  }
  const I operator+(const I &o) const {
    I s;
    s._l = _l, s._r = o._r;
    for (int i = 0; i < 2; ++i) {
      s.c[i] = c[i] + o.c[i];
      s.l[i] = l[i] + !c[!i] * o.l[i];
      s.r[i] = o.r[i] + !o.c[!i] * r[i];
      s.m[i] = max(max(m[i], o.m[i]), r[i] + o.l[i]);
    }
    return s;
  }
  const I &operator+=(const T &t) {
    if (~t.ta) {
      c[t.ta] = l[t.ta] = r[t.ta] = m[t.ta] = _r - _l + 1;
      c[!t.ta] = l[!t.ta] = r[!t.ta] = m[!t.ta] = 0;
    }
    if (t.tr) {
      swap(c[0], c[1]), swap(l[0], l[1]), swap(r[0], r[1]), swap(m[0], m[1]);
    }
    return *this;
  }
};
struct E {
  I v;
  T t;
} e[kN << 2];
int n, q;

void B(int x, int l, int r) {
  if (l == r) {
    e[x].v._l = e[x].v._r = l;
    int v;
    cin >> v;
    e[x].v += T(v);
    return;
  }
  int m = l + r >> 1;
  B(x * 2, l, m), B(x * 2 + 1, m + 1, r);
  e[x].v = e[x * 2].v + e[x * 2 + 1].v;
}
void U(int x, T v) { e[x].v += v, e[x].t += v; }
void U(int x, int l, int r, T v) {
  if (e[x].v._l == l && e[x].v._r == r) {
    U(x, v);
    return;
  }
  U(x * 2, e[x].t), U(x * 2 + 1, e[x].t), e[x].t = T();
  if (l <= e[x * 2].v._r) {
    U(x * 2, l, min(r, e[x * 2].v._r), v);
  }
  if (e[x * 2 + 1].v._l <= r) {
    U(x * 2 + 1, max(l, e[x * 2 + 1].v._l), r, v);
  }
  e[x].v = e[x * 2].v + e[x * 2 + 1].v;
}
I Q(int x, int l, int r) {
  if (e[x].v._l == l && e[x].v._r == r) {
    return e[x].v;
  }
  U(x * 2, e[x].t), U(x * 2 + 1, e[x].t), e[x].t = T();
  I s = I();
  if (l <= e[x * 2].v._r) {
    s = s + Q(x * 2, l, min(r, e[x * 2].v._r));
  }
  if (e[x * 2 + 1].v._l <= r) {
    s = s + Q(x * 2 + 1, max(l, e[x * 2 + 1].v._l), r);
  }
  return s;
}

int main() {
  cin >> n >> q;
  B(1, 1, n);
  for (int o, l, r; q--; ) {
    cin >> o >> l >> r;
    ++l, ++r;
    if (o <= 2) {
      U(1, l, r, {o == 2 ? -1 : o, o == 2});
    } else {
      I s = Q(1, l, r); 
      cout << (o == 3 ? s.c[1] : s.m[1]) << '\n';
    }
  }
  return 0;
}

例子 2：bzoj 4695

#include <algorithm>
#include <iostream>

using namespace std;
using LL = long long;

const int kN = 5e5 + 1;
const int kI = 7e8;

struct T {
  int ad, ax, an;

  T(int ad = 0, int ax = 0, int an = 0) : ad(ad), ax(ax), an(an) {}
  const T operator=(const T &o) { return ad = o.ad, ax = o.ax, an = o.an, *this; }
  const T operator+=(const T &o) { return ad += o.ad, ax += o.ax, an += o.an, *this; }
};
struct E {
  int l, m, r;
  LL sm;
  int mx, sx, cx;
  int mn, sn, cn;
  T tg;

  E() : mx(-kI), sx(-kI), mn(kI), sn(kI) {}
  const E operator=(const E &o) {
    sm = o.sm, mx = o.mx, sx = o.sx, cx = o.cx, mn = o.mn, sn = o.sn, cn = o.cn;
    return *this;
  }
  const E operator+(const E &o) const {
    E p;
    p.sm = sm + o.sm;
    int ax[4] = {mx, sx, o.mx, o.sx};
    sort(ax, ax + 4);
    int lx = unique(ax, ax + 4) - ax - 1;
    p.mx = ax[lx], p.sx = (lx ? ax[lx - 1] : -kI), p.cx = (p.mx == mx) * cx + (p.mx == o.mx) * o.cx;
    int an[4] = {mn, sn, o.mn, o.sn};
    sort(an, an + 4);
    int ln = unique(an, an + 4) - an - 1;
    p.mn = an[0], p.sn = (ln ? an[1] : kI), p.cn = (p.mn == mn) * cn + (p.mn == o.mn) * o.cn;
    return p;
  }
  const E operator+=(T o) {
    if (mx == mn) {  // size==1
      LL v = o.ax - o.ad + o.an;
      sm += 1LL * v * cx;
      mx += v, mn += v;
    } else if (mx == sn) {  // size==2
      sm += 1LL * o.ax * cx + 1LL * o.an * cn;
      mx += o.ax, sn += o.ax, mn += o.an, sx += o.an;
    } else {  // size>=3
      sm += 1LL * o.ax * cx + 1LL * o.an * cn + 1LL * o.ad * (r - l + 1 - cx - cn);
      mx += o.ax, mn += o.an, sx += o.ad, sn += o.ad;
    }
    tg += o;
    return *this;
  }
} e[kN << 2];
int n, q;

void B(int x, int l, int r) {
  e[x].l = l, e[x].r = r, e[x].m = l + r >> 1;
  if (l == r) {
    LL v;
    cin >> v;
    e[x].sm = e[x].mx = e[x].mn = v, e[x].cx = e[x].cn = 1;
    return;
  }
  B(x * 2, e[x].l, e[x].m), B(x * 2 + 1, e[x].m + 1, e[x].r);
  e[x] = e[x * 2] + e[x * 2 + 1];
}
void Pd(int x) {
  T &t = e[x].tg;
  E &l = e[x * 2], &r = e[x * 2 + 1];
  int mx = max(l.mx, r.mx), mn = min(l.mn, r.mn);
  l += T(t.ad, l.mx == mx ? t.ax : t.ad, l.mn == mn ? t.an : t.ad);
  r += T(t.ad, r.mx == mx ? t.ax : t.ad, r.mn == mn ? t.an : t.ad);
  t = T();
}
void Add(int x, int l, int r, LL v) {
  if (e[x].l == l && e[x].r == r) {
    e[x] += T(v, v, v);
    return;
  }
  Pd(x);
  if (l <= e[x].m) {
    Add(x * 2, l, min(r, e[x].m), v);
  }
  if (e[x].m < r) {
    Add(x * 2 + 1, max(l, e[x].m + 1), r, v);
  }
  e[x] = e[x * 2] + e[x * 2 + 1];
}
void _Min(int x, int v) {
  if (e[x].mx <= v) {
    return;
  }
  if (e[x].sx < v) {
    e[x] += T(0, v - e[x].mx, 0);
    return;
  }
  Pd(x), _Min(x * 2, v), _Min(x * 2 + 1, v);
  e[x] = e[x * 2] + e[x * 2 + 1];
}
void Min(int x, int l, int r, int v) {
  if (e[x].l == l && e[x].r == r) {
    _Min(x, v);
    return;
  }
  Pd(x);
  if (l <= e[x].m) {
    Min(x * 2, l, min(r, e[x].m), v);
  }
  if (e[x].m < r) {
    Min(x * 2 + 1, max(l, e[x].m + 1), r, v);
  }
  e[x] = e[x * 2] + e[x * 2 + 1];
}
void _Max(int x, int v) {
  if (e[x].mn >= v) {
    return;
  }
  if (e[x].sn > v) {
    e[x] += T(0, 0, v - e[x].mn);
    return;
  }
  Pd(x), _Max(x * 2, v), _Max(x * 2 + 1, v);
  e[x] = e[x * 2] + e[x * 2 + 1];
}
void Max(int x, int l, int r, int v) {
  if (e[x].l == l && e[x].r == r) {
    _Max(x, v);
    return;
  }
  Pd(x);
  if (l <= e[x].m) {
    Max(x * 2, l, min(r, e[x].m), v);
  }
  if (e[x].m < r) {
    Max(x * 2 + 1, max(l, e[x].m + 1), r, v);
  }
  e[x] = e[x * 2] + e[x * 2 + 1];
}
LL Sum(int x, int l, int r) {
  if (e[x].l == l && e[x].r == r) {
    return e[x].sm;
  }
  Pd(x);
  LL s = 0;
  if (l <= e[x].m) {
    s += Sum(x * 2, l, min(r, e[x].m));
  }
  if (e[x].m < r) {
    s += Sum(x * 2 + 1, max(l, e[x].m + 1), r);
  }
  e[x] = e[x * 2] + e[x * 2 + 1];
  return s;
}
int Max(int x, int l, int r) {
  if (e[x].l == l && e[x].r == r) {
    return e[x].mx;
  }
  Pd(x);
  int s = -kI;
  if (l <= e[x].m) {
    s = max(s, Max(x * 2, l, min(r, e[x].m)));
  }
  if (e[x].m < r) {
    s = max(s, Max(x * 2 + 1, max(l, e[x].m + 1), r));
  }
  e[x] = e[x * 2] + e[x * 2 + 1];
  return s;
}
int Min(int x, int l, int r) {
  if (e[x].l == l && e[x].r == r) {
    return e[x].mn;
  }
  Pd(x);
  int s = kI;
  if (l <= e[x].m) {
    s = min(s, Min(x * 2, l, min(r, e[x].m)));
  }
  if (e[x].m < r) {
    s = min(s, Min(x * 2 + 1, max(l, e[x].m + 1), r));
  }
  e[x] = e[x * 2] + e[x * 2 + 1];
  return s;
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  B(1, 1, n);
  cin >> q;
  for (int o, l, r, v; q--;) {
    cin >> o >> l >> r;
    if (o <= 3) {
      cin >> v;
      if (o == 1) {
        Add(1, l, r, v);
      } else if (o == 2) {
        Max(1, l, r, v);
      } else {
        Min(1, l, r, v);
      }
    } else if (o == 4) {
      cout << Sum(1, l, r) << '\n';
    } else if (o == 5) {
      cout << Max(1, l, r) << '\n';
    } else {
      cout << Min(1, l, r) << '\n';
    }
  }
  return 0;
}