UOJ - #164: V
Historic Informationまわりの勉強で解いた。解法メモ
問題概要
の番号がついたタンクがある。
番目のタンクには最初mの高さの水が入っている。以下のクエリを合計回処理せよ。
- の各タンクの水の高さをm上昇させる
- の各タンクの水の高さをm減少させる (高さは負にならない)
- の各タンクの水の高さをmにする
- タンク の現在の水の高さ(m)を出力
- タンク の過去最大の水の高さ(m)を出力
制約
解法
historic maximal valueを従来の遅延セグ木上で管理する。
のhistoric maximal valueを とする。
この問題は の単点参照のみを行うが、区間最大値を求めるものと考えて解いてみる。
また、各ノードではlazy tagとして以下の値を管理する。
2つのlazy tagの初期値は であり、各操作では以下のtagを更新ノードの2つのlazy tagとマージして更新する。
- を に更新するtag:
- を に更新するtag:
- を に更新するtag:
あるtag , を、あるノードが持つlazy tag , へマージすることを考える。
この時、ノードが持つlazy tagは以下のように更新できる。
また、lazy tagの更新と同時にノードが持つ各最大値を以下のように更新する。
計算量は
実装
提出コード(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; }