Segment Tree Beats(without set and gcd)

#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
}

const int64 INF = 1e18L;

struct node {
  int64 max1, max2, min1, min2, sum, lazy_add;
  int cnt_max, cnt_min;
};

struct SegTree {
  int Size;
  vector<node> tree;

  SegTree(int N) {
    Size = 1;
    while (Size < N)
      Size <<= 1;
    tree.resize(Size << 1);
  }

  node join(const node &a, const node &b) {
    node x;
    x.sum = a.sum + b.sum;
    x.lazy_add = 0;
    if (a.max1 > b.max1) {
      x.max1 = a.max1;
      x.cnt_max = a.cnt_max;
      x.max2 = max(a.max2, b.max1);
    } else {
      if (a.max1 < b.max1) {
        x.max1 = b.max1;
        x.cnt_max = b.cnt_max;
        x.max2 = max(a.max1, b.max2);
      } else {
        x.max1 = a.max1;
        x.cnt_max = a.cnt_max + b.cnt_max;
        x.max2 = max(a.max2, b.max2);
      }
    }
    if (a.min1 < b.min1) {
      x.min1 = a.min1;
      x.cnt_min = a.cnt_min;
      x.min2 = min(a.min2, b.min1);
    } else {
      if (a.min1 > b.min1) {
        x.min1 = b.min1;
        x.cnt_min = b.cnt_min;
        x.min2 = min(a.min1, b.min2);
      } else {
        x.min1 = a.min1;
        x.cnt_min = a.cnt_min + b.cnt_min;
        x.min2 = min(a.min2, b.min2);
      }
    }
    return x;
  }

  void build(int x, int lx, int rx) {
    if (lx == rx) {
      int64 val;
      cin >> val;
      tree[x].max1 = tree[x].min1 = tree[x].sum = val;
      tree[x].max2 = -INF;
      tree[x].min2 = INF;
      tree[x].cnt_max = tree[x].cnt_min = 1;
      tree[x].lazy_add = 0;
      return;
    }
    int mid = (lx + rx) >> 1;
    build(x << 1, lx, mid);
    build(x << 1 | 1, mid + 1, rx);
    tree[x] = join(tree[x << 1], tree[x << 1 | 1]);
  }

  void update_node_max(int x, int64 val) {
    tree[x].sum += (val - tree[x].max1) * tree[x].cnt_max;
    if (tree[x].max1 == tree[x].min1)
      tree[x].max1 = tree[x].min1 = val;
    else {
      if (tree[x].max1 == tree[x].min2)
        tree[x].max1 = tree[x].min2 = val;
      else tree[x].max1 = val;
    }
  }

  void update_node_min(int x, int64 val) {
    tree[x].sum += (val - tree[x].min1) * tree[x].cnt_min;
    if (tree[x].min1 == tree[x].max1)
      tree[x].min1 = tree[x].max1 = val;
    else {
      if (tree[x].min1 == tree[x].max2)
        tree[x].min1 = tree[x].max2 = val;
      else tree[x].min1 = val;
    }
  }

  void update_node_add(int x, int n, int64 val) {
    tree[x].max1 += val;
    if (tree[x].max2 != -INF)
      tree[x].max2 += val;
    tree[x].min1 += val;
    if (tree[x].min2 != INF)
      tree[x].min2 += val;
    tree[x].sum += val * n;
    tree[x].lazy_add += val;
  }

  void push(int x, int lx, int rx) {
    if (lx == rx)
      return;
    int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1;
    int l1 = mid - lx + 1, l2 = rx - mid;
    if (tree[x].lazy_add != 0) {
      update_node_add(lSon, l1, tree[x].lazy_add);
      update_node_add(rSon, l2, tree[x].lazy_add);
      tree[x].lazy_add = 0;
    }
    for (int i = 0; i < 2; ++i) {
      int son = x << 1 | i;
      if (tree[x].max1 < tree[son].max1)
        update_node_max(son, tree[x].max1);
      if (tree[x].min1 > tree[son].min1)
        update_node_min(son, tree[x].min1);
    }
  }

  void update_min(int x, int lx, int rx, int st, int dr, int64 val) {
    if (val >= tree[x].max1)
      return;
    if (st <= lx && rx <= dr && val > tree[x].max2) {
      update_node_max(x, val);
      return;
    }
    push(x, lx, rx);
    int mid = (lx + rx) >> 1;
    if (st <= mid)
      update_min(x << 1, lx, mid, st, dr, val);
    if (mid < dr)
      update_min(x << 1 | 1, mid + 1, rx, st, dr, val);
    tree[x] = join(tree[x << 1], tree[x << 1 | 1]);
  }

  void update_max(int x, int lx, int rx, int st, int dr, int64 val) {
    if (val <= tree[x].min1)
      return;
    if (st <= lx && rx <= dr && val < tree[x].min2) {
      update_node_min(x, val);
      return;
    }
    push(x, lx, rx);
    int mid = (lx + rx) >> 1;
    if (st <= mid)
      update_max(x << 1, lx, mid, st, dr, val);
    if (mid < dr)
      update_max(x << 1 | 1, mid + 1, rx, st, dr, val);
    tree[x] = join(tree[x << 1], tree[x << 1 | 1]);
  }

  void update_add(int x, int lx, int rx, int st, int dr, int64 val) {
    if (st <= lx && rx <= dr) {
      update_node_add(x, rx - lx + 1, val);
      return;
    }
    push(x, lx, rx);
    int mid = (lx + rx) >> 1;
    if (st <= mid)
      update_add(x << 1, lx, mid, st, dr, val);
    if (mid < dr)
      update_add(x << 1 | 1, mid + 1, rx, st, dr, val);
    tree[x] = join(tree[x << 1], tree[x << 1 | 1]);
  }

  int64 query_sum(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr)
      return tree[x].sum;
    push(x, lx, rx);
    int mid = (lx + rx) >> 1;
    int64 ans = 0;
    if (st <= mid)
      ans += query_sum(x << 1, lx, mid, st, dr);
    if (mid < dr)
      ans += query_sum(x << 1 | 1, mid + 1, rx, st, dr);
    return ans;
  }
};

void solve() {
  int N, Q;
  cin >> N >> Q;
  SegTree tree(N);
  tree.build(1, 1, N);
  for (int q = 0; q < Q; ++q) {
    int op, l, r;
    int64 x;
    cin >> op >> l >> r;
    ++l;
    if (op < 3)
      cin >> x;
    if (op == 0)
      tree.update_min(1, 1, N, l, r, x);
    else {
      if (op == 1)
        tree.update_max(1, 1, N, l, r, x);
      else {
        if (op == 2)
          tree.update_add(1, 1, N, l, r, x);
        else cout << tree.query_sum(1, 1, N, l, r) << '\n';
      }
    }
  }
}

int main() {
  fastIO();
  solve();
  return 0;
}