Gorgeous Sequence: 区間最小値更新・区間最大値・区間和

長さ \(n\) の数列に対して次の操作をサポートする：

• 0 l r v: 区間 \([l, r]\) の要素を \(v\) との最小値で更新
• 1 l r: 区間の最大値を取得
• 2 l r: 区間の和を取得

各ノードで最大値・最大値の出現回数・二番目の最大値を管理。更新時：

1. \(mx \leq v\): 処理不要
2. \(smx < v < mx\): 最大値のみ更新
3. \(v \leq smx\): 子ノードで再帰処理

struct SegNode {
  int left, right, max_val, max_cnt, sec_max, tag;
  long long sum;
  SegNode() : left(0), right(0), max_val(-1), max_cnt(0), 
              sec_max(-1), tag(-1), sum(0) {}
};

SegNode tree[MAX_NODES];
int node_count, root;

void update_node(int node) {
  tree[node].sum = tree[tree[node].left].sum + tree[tree[node].right].sum;
  
  int lmax = tree[tree[node].left].max_val;
  int rmax = tree[tree[node].right].max_val;
  
  if (lmax == rmax) {
    tree[node].max_val = lmax;
    tree[node].max_cnt = tree[tree[node].left].max_cnt + 
                         tree[tree[node].right].max_cnt;
    tree[node].sec_max = std::max(tree[tree[node].left].sec_max, 
                                 tree[tree[node].right].sec_max);
  } else if (lmax > rmax) {
    tree[node].max_val = lmax;
    tree[node].max_cnt = tree[tree[node].left].max_cnt;
    tree[node].sec_max = std::max(tree[tree[node].left].sec_max, rmax);
  } else {
    tree[node].max_val = rmax;
    tree[node].max_cnt = tree[tree[node].right].max_cnt;
    tree[node].sec_max = std::max(tree[tree[node].right].sec_max, lmax);
  }
}

void apply_tag(int node, int val) {
  if (tree[node].max_val <= val) return;
  tree[node].sum += (long long)tree[node].max_cnt * (val - tree[node].max_val);
  tree[node].max_val = val;
  tree[node].tag = val;
}

void propagate(int node) {
  if (tree[node].tag != -1) {
    apply_tag(tree[node].left, tree[node].tag);
    apply_tag(tree[node].right, tree[node].tag);
    tree[node].tag = -1;
  }
}

void range_min(int l, int r, int ql, int qr, int val, int node) {
  if (tree[node].max_val <= val) return;
  if (ql <= l && r <= qr && tree[node].sec_max < val) {
    apply_tag(node, val);
    return;
  }
  int mid = (l + r) / 2;
  propagate(node);
  if (ql <= mid) range_min(l, mid, ql, qr, val, tree[node].left);
  if (qr > mid) range_min(mid+1, r, ql, qr, val, tree[node].right);
  update_node(node);
}

拡張機能: 区間加算・区間最小値更新

区間加算・区間最小値更新・点挿入・総和取得をサポート。加算と最小値更新の相互作用を管理：

struct AdvNode {
  int left, right, count, min_val, min_cnt, sec_min, add_tag, min_tag;
  long long sum;
  AdvNode() : left(0), right(0), count(0), min_val(INT_MAX), min_cnt(0),
              sec_min(INT_MAX), add_tag(0), min_tag(INT_MAX), sum(0) {}
};

void apply_add(int node, int val) {
  if (!tree[node].count) return;
  tree[node].sum += (long long)tree[node].count * val;
  tree[node].min_val += val;
  if (tree[node].sec_min != INT_MAX) tree[node].sec_min += val;
  tree[node].add_tag += val;
  if (tree[node].min_tag != INT_MAX) tree[node].min_tag += val;
}

void apply_min(int node, int val) {
  if (!tree[node].count || tree[node].min_val >= val) return;
  tree[node].sum += (long long)tree[node].min_cnt * (val - tree[node].min_val);
  tree[node].min_val = val;
  tree[node].min_tag = val;
}

void propagate_adv(int node) {
  if (tree[node].add_tag) {
    apply_add(tree[node].left, tree[node].add_tag);
    apply_add(tree[node].right, tree[node].add_tag);
    tree[node].add_tag = 0;
  }
  if (tree[node].min_tag != INT_MAX) {
    apply_min(tree[node].left, tree[node].min_tag);
    apply_min(tree[node].right, tree[node].min_tag);
    tree[node].min_tag = INT_MAX;
  }
}