AtCoder Grand Contest AGC005 B - Minimum Sum
B - Minimum Sum
解説
区間がたくさん与えられるので、その中のある値の和を求めよという問題は多くありますが、基本的に区間をすべて列挙して解くことはできません。今回も例によってそのパターンで、ある値が、いくつの区間の値になるかを求める問題だと捉えることでソリューションを見出します。いわゆる寄与ゲー、主客転倒と言われる部類の問題です。
ある値が最小値になる区間は、左右に広がっているので、その境界を二分探索することでうまくいきます。左右の境界が求まったら、左右の境界の組み合わせが寄与する個数になるので、で解くことができました。
実装
template<typename T> class SegTree { public: int N;//葉の数 vector<T> data;//配列 T unit;//単位元 function<T(T,T)> op;//区間クエリで使う処理 function<T(T,T)> update;//点更新で使う処理 T _query(int a, int b, int k, int l, int r) { if(r <= a || b <= l)return unit; if(a <= l && r <= b){ return data[k]; } else{ T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2); //左の子 T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r); //左の子 return op(c1, c2); } } //コンストラクター //_N: 必要サイズ, _unit: 初期値かつ単位元, _op: クエリ関数, _update: 更新関数 SegTree(int _N, T _unit, function<T(T, T)> _op, function<T(T, T)> _update) :unit(_unit), op(_op), update(_update){ N = 1; while(N < _N)N *= 2; data.assign(2 * N - 1, unit); } //i(0-indexed)の値にupdate関数を適用 void change(int i, T x){ i += N - 1; data[i] = update(data[i], x); while(i > 0){ i = (i - 1) / 2; data[i] = op(data[i * 2 + 1], data[i * 2 + 2]); } } //[a, b)の区間クエリの実行 T query(int a, int b){ return _query(a, b, 0, 0, N); } //添字でアクセス T operator[](int i) { return data[i + N - 1]; } }; int main(){ int N; cin >> N; long long inf = (1LL << 31) - 1; auto f = [&](long long a, long long b){ return min(a, b); }; auto g = [&](long long a, long long b){ return b; }; SegTree<long long> Tree(N,inf,f,g); vector<ll> A(N); rep(i, N)cin >> A[i]; rep(i,N)Tree.change(i, A[i]); auto checkl = [&](int l, int r) -> bool{ return Tree.query(l,r) == A[r-1]; }; auto checkr = [&](int l, int r) -> bool{ return Tree.query(l,r) == A[l]; }; ll ans = 0; rep(i,N){ // calc 左端と右端を計算する O(logN) ll l, r; { int ng = -1; int ok = i; while(ok - ng > 1){ int mid = (ok + ng) >> 1; if(checkl(mid, i+1))ok = mid; else ng = mid; } l = i+1 - ok; } { int ok = i+1; int ng = N+1; while(ng - ok > 1){ int mid = (ok + ng) >> 1; if(checkr(i,mid))ok = mid; else ng = mid; } r = ok - i; } ll cnt = l * r; ans += cnt * A[i]; } cout << ans << endl; }