BOJ 25639 - 수열과 최대 상승 쿼리

BOJ 25639 - 수열과 최대 상승 쿼리

금광세그의 쉬운버전이고,

어떤 노드에서 구간 최소값, 최대값, $\text{Max}(a_j-a_i) ~ (l \le i \le j \le r)$ 을 저장하게 한다.

struct node {
   int mn = 1e9, mx = -1e9, hv = 0;
   node operator+(const node &o) const {
      node ret;

      ret.mn = min(mn, o.mn);
      ret.mx = max(mx, o.mx);
      ret.hv = max({hv, o.hv, o.mx - mn});

      return ret;
   }
};

struct seg_tree {
   int N;
   vector<node> tree;
   seg_tree(int N) : N(N) {
      int size = 1 << int(ceil(log2(N)) + 1);
      tree.resize(size);
   }
   void update(int n, int nl, int nr, int i, int k) {
      if (i < nl || i > nr) return;
      if (nl == nr) {
         tree[n] = {k, k, 0};
         return;
      }
      int m = (nl + nr) >> 1;
      update(n * 2, nl, m, i, k);
      update(n * 2 + 1, m + 1, nr, i, k);
      tree[n] = tree[n * 2] + tree[n * 2 + 1];
   }
   node query(int n, int nl, int nr, int l, int r) {
      if (r < nl || l > nr) return {};
      if (nl >= l && nr <= r) return tree[n];
      int m = (nl + nr) >> 1;
      return query(n * 2, nl, m, l, r) + query(n * 2 + 1, m + 1, nr, l, r);
   }
};

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   seg_tree seg(n);
   for (int i = 0; i < n; i++) seg.update(1, 0, n - 1, i, a[i]);
   int q;
   cin >> q;
   while (q--) {
      int cmd, k, x;
      cin >> cmd >> k >> x;
      if (cmd == 1) {
         k--;
         seg.update(1, 0, n - 1, k, x);
      } else {
         k--, x--;
         cout << seg.query(1, 0, n - 1, k, x).hv << endl;
      }
   }
}