日々drdrする人のメモ

今日も明日もdrdr

UOJ - #164: V

Historic Informationまわりの勉強で解いた。解法メモ

uoj.ac

問題概要

 1, 2, ..., Nの番号がついたタンクがある。

 i番目のタンクには最初 a_imの高さの水が入っている。以下のクエリを合計 M回処理せよ。

  1.  i \in [l, r] の各タンクの水の高さを xm上昇させる
  2.  i \in [l, r] の各タンクの水の高さを xm減少させる (高さは負にならない)
  3.  i \in [l, r] の各タンクの水の高さを xmにする
  4. タンク y の現在の水の高さ(m)を出力
  5. タンク y の過去最大の水の高さ(m)を出力

制約

  •  1 \le N, M \le 5 \times 10^5
  •  0 \le a_i \le 10^9
  •  0 \le x \le 10^9

解法

historic maximal valueを従来の遅延セグ木上で管理する。

 a_i のhistoric maximal value b_i とする。
この問題は  a_i, b_i の単点参照のみを行うが、区間最大値を求めるものと考えて解いてみる。

各ノードでは、 a_i区間最大値 A b_i区間最大値 B を管理する。

また、各ノードではlazy tagとして以下の値を管理する。

  •  a_i区間最大値 Aを更新するためのlazy tag:  (a, b)
    • 関数  f_{(a, b)}(x) = \max(x+a, b) のパラメータ
  •  b_i区間最大値 Bを更新するためのlazy tag:  (a_H, b_H)
    • 関数  h_{(a_H, b_H)}(x) = \max(x + a_H, b_H) のパラメータ

2つのlazy tagの初期値は  (0, -\infty) であり、各操作では以下のtagを更新ノードの2つの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)へマージすることを考える。
この時、ノードが持つlazy 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))

また、lazy tagの更新と同時にノードが持つ各最大値を以下のように更新する。

  •  a_i区間最大値 A f_{(c, d)}(A) に更新
  •  b_i区間最大値 B \max(B, h_{(c_H, d_H)}(A)) に更新

計算量は  O(M \log N)

実装

提出コード(C++11): 提交记录 #348754 - Universal Online Judge

#include<algorithm>
#include<iostream>
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; }

    // f_{(a, b)}(x) を求める
    inline ll calc(ll x) const { return max(x + a, b); }

    // h_{(a_H, b_H)}(x) を求める
    inline ll hcalc(ll x) const { return max(x + ha, hb); }

    // tag t とマージする
    inline void merge(Tag &t) {
      // -inf の値は -inf を維持するように更新する
      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);
    }

    // lazy tagの初期化
    inline void clear() { a = ha = 0; b = hb = -inf; }

    // 伝搬すべきtagか
    inline bool empty() const { return a == 0 && b == -inf; }
  };

  int n0;

  //  max_v[k]: ノードkの a_i の区間最大値
  // hmax_v[k]: ノードkの b_i の区間最大値
  ll max_v[2*N], hmax_v[2*N];

  // lazy: ノードkが持つlazy tag
  Tag lazy[2*N];

  // ノードkから子ノードへpushdown
  void push(int k) {
    if(n0-1 <= k) return;

    if(!lazy[k].empty()) {
      // ノードkが持つlazy tagをノード2k+1, 2k+2に伝搬してマージ

      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();
    }
  }

  // ノードkの情報を更新
  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]);
  }

  // a_i の区間最大値を取得
  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);
  }

  // a_i を a_i + x に更新
  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 (x, -∞)
      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);
  }

  // a_i を x に更新
  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 (-∞, x)
      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);
  }

  // a_i を max(a_i, x) に更新
  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 (0, x)
      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);
  }

  // b_i の区間最大値を取得
  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);
  }

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

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

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

  ll query_max(int a, int b) {
    return _query_max(a, b, 0, 0, n0);
  }

  ll query_hmax(int a, int b) {
    return _query_hmax(a, b, 0, 0, n0);
  }
};

int n, m;
ll a[N];

int main() {
  cin.tie(0); ios::sync_with_stdio(false);

  cin >> n >> m;
  for(int i=0; i<n; ++i) cin >> a[i];
  SegmentTree st(n, a);

  while(m--) {
    int t, l, r, x, y;
    cin >> t;
    switch(t) {
      case 1:
        // a_i ← a_i + x
        cin >> l >> r >> x;
        st.add_val(l-1, r, x);
        break;
      case 2:
        // a_i ← max(a_i - x, 0)
        cin >> l >> r >> x;
        st.add_val(l-1, r, -x);
        st.update_max(l-1, r, 0);
        break;
      case 3:
        // a_i ← x
        cin >> l >> r >> x;
        st.update_val(l-1, r, x);
        break;
      case 4:
        // a_y の値を出力
        cin >> y;
        cout << st.query_max(y-1, y) << "\n";
        break;
      case 5:
        // b_y の値を出力
        cin >> y;
        cout << st.query_hmax(y-1, y) << "\n";
        break;
    }
  }
  return 0;
}