CSAcademy Round#53 C

CSAのソースコードのリンクが貼れない(わからない)ので久しぶりにブログに...(この記事は以前あったものを色々あって修正し直したものです)

CSAcademy #Round53 - C(Histogram Partition)

N個の色んな数字からなるAという配列とN個の要素すべてが0の配列Bがあるので, Bのある区間の要素全てに1を足す, という操作をできるだけ少ない回数でAを作りなさい, という問題(答えるのはその回数).

これを, BからAにするのではなく, AからBにする. 初期区間[l, r)を[0, n)として, 1. 現在の区間の最小値を取ってくる(複数ある場合は一番左). 2. 最小値を現在の区間から引き, その最小値の位置をkとすると, [l, k)と[k+1, r)に分割し, それぞれについて1を行う. 最小値が0ならばさらにそこで分割する. 3. これをAの要素すべてが0となるまで行う. このときの操作回数が答え.これをセグメントツリーと分割統治法でやる. 最初はStarrySky木でやろうとしたけどすんごいバグらせたのでセグメントツリーに変えた. 想定解はstackを使ってO(N)でした(すごい).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define fi first
#define se second

using ll = long long;

// first : value, second : id

template <typename T>
class SegmentTree {
private:
  int n;
  T _init;
  vector<T> seg;
 
  int size (int N) {
    int ret;
    for (ret = 1; ret < N; ret <<= 1);
    return ret;
  }
 
  T query(int a, int b, int k, int l, int r) {
    if (r <= a or b <= l) return _init;
    if (a <= l and r <= b) return seg[k];
 
    T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return min(vl, vr);
  }
 
public:
  SegmentTree (int N, T i = 0) : n(size(N)), seg(size(N) * 2, i), _init(i) {}
  SegmentTree () {}
 
  void Init(int N, T i) {
      n = size(N);
      seg.resize(size(N) * 2 - 1, i);
      _init = i;
  }
 
  void Update (int k, T val) {
    k += n - 1;
    seg[k] = val;
    while (k > 0) {
      k = (k - 1) / 2;
      // 適宜変更
      seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]);
    }
  }
 
  // [l, r) 開区間であることに注意!!! ... [l, r]ならfind(l, r + 1)
  T Find(int l, int r) {
    return query(l, r, 0, 0, n);
  }
};
int n, a;
SegmentTree<pair<int, int> > segtree;

ll solve(int l, int r, int d);

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

    cin >> n;
    segtree.Init(n, {int(1e9), int(1e9)});
    
    for (int i = 0; i < n; ++i) {
        cin >> a;
        segtree.Update(i, {a, i});
    }

    int l = 0, r = n;

    ll ans = solve(l, r, 0);
    
    cout << ans << endl;
    
    return 0;
}


ll solve(int l, int r, int d) {
    if (l >= r) return 0;
    
    ll ret = 0;

    pair<int, int> p = segtree.Find(l, r);

    if (!(l <= p.se and p.se < r)) return 0;

    if (p.fi - d == 0) {
        ret += solve(l, p.se, d);
        ret += solve(p.se + 1, r, d);
    }
    else {
        ret += 1;
        ret += solve(l, p.se, p.fi);
        ret += solve(p.se + 1, r, p.fi);
    }

    return ret;
}