histric maximal valueのRMQ (遅延評価セグメント木)

histric maximal value (histric information) on Segment Tree with Lazy Propagation

概要

以下のクエリが処理できる遅延セグメント木の実装

数列 \(A = a_1, ..., a_N\) は現在の値、数列 \(B = b_1, ..., b_N\) は各 \(a_i\) の過去最大値とする。

\(a_i\) の値を \(a_i + x\) に更新
\(a_i\) の値を \(x\) に更新
\(a_i\) の値を \(\max(a_i, x)\) に更新
\(a_l, a_{l+1}, ..., a_{r-1}\) の最大値を求める
\(b_l, b_{l+1}, ..., b_{r-1}\) の最大値を求める

実装説明

各ノードのlazy tagとして以下の値を管理することを考える。

\(a_i\) の区間最大値を伝搬するためのlazy tag: \((a, b)\)
\(b_i\) の区間最大値を伝搬するためのlazy tag: \((a_H, b_H)\)

各tagは \(f_{(a, b)}(x) = \max(x+a, b)\), \(h_{(a_H, b_H)}(x) = \max(x + a_H, b_H)\) を計算するための関数のパラメータとする。

lazy tagの初期値は \((0, -\infty)\) になる。各クエリ操作では以下のtagで更新ノードのlazy tagを更新する。

\(a_i\) を \(a_i + x\) に更新するtag: \((x, -\infty)\)
\(a_i\) を \(x\) に更新するtag: \((-\infty, x)\)
\(a_i\) を \(\max(a_i, x)\) に更新するtag: \((0, x)\)

tag \((c, d)\), \((c_H, d_H)\) の情報を、あるノードのlazy tag \((a, b)\), \((a_H, b_H)\) へマージすることを考える。

この時、ノードが持つtagは以下のように更新できる。

\((a, b) \leftarrow (a+c, \max(b+c, d))\)
\((a_H, b_H) \leftarrow (\max(a_H, a+c_H), \max(b_H, b+c_H, d_H))\)

同時に、子ノードの \(a_i\) の区間最大値 \(A\) を \(f_{(c, d)}(A)\), \(b_i\) の区間最大値 \(B\) を \(\max(B, h_{(c_H, d_H)}(A))\) に更新する。

計算量

各クエリ操作: \(O(\log N)\)

実装

#include<algorithm>
using namespace std;
typedef long long ll;

#define N (1 << 19)

class SegmentTree {
  static const ll inf = 1e18;

  struct Tag {
    ll ha, hb, a, b;

    Tag() {}

    Tag(ll a, ll b) : a(a), b(b) { ha = a; hb = b; }

    ll calc(ll x) const { return max(x + a, b); }
    ll hcalc(ll x) const { return max(x + ha, hb); }

    void merge(Tag &t) {
      if(a != -inf && t.ha != -inf) ha = max(ha, a + t.ha);
      if(b != -inf && t.ha != -inf) hb = max(hb, b + t.ha);
      hb = max(hb, t.hb);

      a = (a != -inf && t.a != -inf ? a + t.a : -inf);
      b = (b != -inf && t.a != -inf ? max(b + t.a, t.b) : t.b);
    }

    void clear() { a = ha = 0; b = hb = -inf; }

    bool empty() const { return a == 0 && b == -inf; }
  };

  int n0;
  ll max_v[2*N], hmax_v[2*N];
  Tag lazy[2*N];

  void push(int k) {
    if(n0-1 <= k) return;

    if(!lazy[k].empty()) {
      hmax_v[2*k+1] = max(hmax_v[2*k+1], lazy[k].hcalc(max_v[2*k+1]));
      max_v[2*k+1] = lazy[k].calc(max_v[2*k+1]);
      lazy[2*k+1].merge(lazy[k]);

      hmax_v[2*k+2] = max(hmax_v[2*k+2], lazy[k].hcalc(max_v[2*k+2]));
      max_v[2*k+2] = lazy[k].calc(max_v[2*k+2]);
      lazy[2*k+2].merge(lazy[k]);

      lazy[k].clear();
    }
  }

  void update(int k) {
    max_v[k] = max(max_v[2*k+1], max_v[2*k+2]);
    hmax_v[k] = max(hmax_v[2*k+1], hmax_v[2*k+2]);
  }

  ll _query_max(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return -inf;
    }
    if(a <= l && r <= b) {
      return max_v[k];
    }
    push(k);
    ll lv = _query_max(a, b, 2*k+1, l, (l+r)/2);
    ll rv = _query_max(a, b, 2*k+2, (l+r)/2, r);
    return max(lv, rv);
  }

  void _add_val(ll x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return;
    }
    if(a <= l && r <= b) {
      Tag t = Tag(x, -inf);
      hmax_v[k] = max(hmax_v[k], t.hcalc(max_v[k]));
      max_v[k] = t.calc(max_v[k]);
      lazy[k].merge(t);
      return;
    }

    push(k);
    _add_val(x, a, b, 2*k+1, l, (l+r)/2);
    _add_val(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }

  void _update_val(ll x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return;
    }
    if(a <= l && r <= b) {
      Tag t = Tag(-inf, x);
      hmax_v[k] = max(hmax_v[k], t.hcalc(max_v[k]));
      max_v[k] = t.calc(max_v[k]);
      lazy[k].merge(t);
      return;
    }

    push(k);
    _update_val(x, a, b, 2*k+1, l, (l+r)/2);
    _update_val(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }

  void _update_max(ll x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return;
    }
    if(a <= l && r <= b) {
      Tag t = Tag(0, x);
      hmax_v[k] = max(hmax_v[k], t.hcalc(max_v[k]));
      max_v[k] = t.calc(max_v[k]);
      lazy[k].merge(t);
      return;
    }

    push(k);
    _update_max(x, a, b, 2*k+1, l, (l+r)/2);
    _update_max(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }

  ll _query_hmax(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return -inf;
    }
    if(a <= l && r <= b) {
      return hmax_v[k];
    }
    push(k);
    ll lv = _query_hmax(a, b, 2*k+1, l, (l+r)/2);
    ll rv = _query_hmax(a, b, 2*k+2, (l+r)/2, r);
    return max(lv, rv);
  }

public:
  SegmentTree(int n, ll *a) {
    n0 = 1;
    while(n0 < n) n0 <<= 1;

    for(int i=0; i<2*n0-1; ++i) lazy[i].clear();

    for(int i=0; i<n; ++i) max_v[n0-1+i] = hmax_v[n0-1+i] = a[i];
    for(int i=n; i<n0; ++i) max_v[n0-1+i] = hmax_v[n0-1+i] = -inf;

    for(int i=n0-2; i>=0; --i) update(i);
  }

  // range add query
  void add_val(int a, int b, ll x) {
    _add_val(x, a, b, 0, 0, n0);
  }

  // range update query
  void update_val(int a, int b, ll x) {
    _update_val(x, a, b, 0, 0, n0);
  }

  // range maximize query
  void update_max(int a, int b, ll x) {
    _update_max(x, a, b, 0, 0, n0);
  }

  // range maximum query
  ll query_max(int a, int b) {
    return _query_max(a, b, 0, 0, n0);
  }

  // (historic maximal value) range maximum query
  ll query_hmax(int a, int b) {
    return _query_hmax(a, b, 0, 0, n0);
  }
};

Verified

UOJ: "#164. 【清华集训2015】V": source (C++11, 5393ms)
BZOJ: "3064: Tyvj 1518 CPU监控" (C++, 19328ms)

戻る