Submission #2753962

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

template<class Monoid, class OperatorMonoid = Monoid>
struct LazySegmentTree {
  using FunctionM = function< Monoid(Monoid, Monoid) >;
  using FunctionMO = function< Monoid(Monoid, OperatorMonoid, int) >; // 3rd param = length;
  using FunctionO = function < OperatorMonoid(OperatorMonoid, OperatorMonoid) >;

  int N; vector<Monoid> segment; vector<OperatorMonoid> lazy;
  const FunctionM FuncM; const FunctionMO FuncMO; const FunctionO FuncO;
  const Monoid idM; const OperatorMonoid idOM;

  LazySegmentTree(int n, const FunctionM FuncM, const FunctionMO FuncMO, const FunctionO FuncO,
    const Monoid idM, const OperatorMonoid idOM)
  : FuncM(FuncM), FuncMO(FuncMO), FuncO(FuncO), idM(idM), idOM(idOM) {
    N = 1;
    while (N < n) N <<= 1;
    segment.assign(2 * N, idM); lazy.assign(2 * N, idOM);
  }

  void set(int num, Monoid x) {
    segment[N + num] = x;
  }
  void build() {
    for (int k = N - 1; k > 0; k--) {
      segment[k] = FuncM(segment[2*k], segment[2*k+1]);
    }
  }

  void propagate(int k, int len){
    if (lazy[k] != idOM) {
      if (k < N) {
        lazy[2*k] = FuncO(lazy[2*k], lazy[k]);
        lazy[2*k+1] = FuncO(lazy[2*k+1], lazy[k]);
      }
      segment[k] = FuncMO(segment[k], lazy[k], len);
      lazy[k] = idOM;
    }
  }

  Monoid update(int a, int b, const OperatorMonoid x) {
    return update(a, b, x, 1, 0, N);
  }
  Monoid update(int a, int b, const OperatorMonoid x, int k, int l, int r){
    propagate(k, r-l);
    if (b <= l || r <= a) {
      return segment[k];
    } else if (a <= l && r <= b) {
      lazy[k] = FuncO(lazy[k], x);
      propagate(k, r-l);
      return segment[k];
    } else {
      int m = (l + r) / 2;
      return segment[k] = FuncM(update(a, b, x, 2*k, l, m), update(a, b, x, 2*k+1, m, r));
    }
  }

  Monoid query(int a, int b) {
    return query(a, b, 1, 0, N);
  }
  Monoid query(int a, int b, int k, int l, int r) {
    propagate(k, r-l);
    if (b <= l || r <= a) {
      return idM;
    } else if (a <= l && r <= b) {
      return segment[k];
    } else {
      int m = (l + r) / 2;
      return FuncM(query(a, b, 2*k, l, m), query(a, b, 2*k+1, m, r));
    }
  }

  // 0-indexed numbering;
  Monoid operator[](const int &k) {
    return query(k, k + 1);
  }
};

int F(int a, int b) {return a + b;}; // sum
int G(int a, int b, int len) {return len - a;}; // bit inversion (xor 1)
int H(int a, int b) {return a xor b;}; // xor

int main(){
  int n, q; cin >> n >> q;
  LazySegmentTree<int> lst(n, F, G, H, 0, 0);
  for (int i = 0; i < q; i++) {
    int a, b, c; cin >> a >> b >> c;
    if (a == 1) lst.update(b, c, 1);
    else cout << lst.query(b, c) << endl;
  }
  return 0;
}

Submission Info

Judge Result