---
tags: IOI
---
# IOI2007 Day1-3 帆 (Sails)

## 問題文

https://www.ioi-jp.org/ioi/2007/problem/day1/sails-prob-j.pdf
https://oj.uz/problem/view/IOI07_sails

船に $N$ 本の柱が立っていて、 $i$ 本目の柱の高さは $H_i$ です。
柱は $H_i$ 個の区間に分かれていて、そのうち $K_i$ 個を選んで、帆を張ります。
ある帆の**非効率さ**を その帆と同じ高さで、かつ前にある帆の数とします。
帆の**非効率さ**の総和の最小値を求めてください。
$N ≤ 100000$

## 考察

コストが $\Theta($帆の数$^2)$ なので、帆の数は平坦にしたほうがいい。
また、柱の順番は関係ないので、ソートしていい感じにできて、
$H$ の昇順にすると、帆の数が少ないところに貪欲に入れることになる。

よって、次ができれば良い。

> 空の multiset があります
> 以下のクエリを処理した後の multiset を答えてください
> - $0$ を追加する
> - 小さい方から $K_i$ 個選び、$1$ 増やす

これは要素の挿入・削除と区間和ができる平衡二分木を自作して、
cnt[i] := (multiset 内の i の個数) とすれば $O(N \log N)$ でできる。
自作平衡二分木はやりたくないので、挿入と削除のできる __gnu_cxx::rope を頑張って使う。
区間和は累積和を持てばできる。

## 実装

__gnu_cxx::rope のリファレンスがないのでかなり苦戦した。
__gnu_cxx::rope< pair<T, U> > を使うと CE になるという罠がある。
$O(N(\log N)^2)$　637ms / 1000ms
https://oj.uz/submission/212762

## ところで

__gnu_cxx::rope はGCC拡張だし、平衡二分木の自作はシラバス外なので、もっとうまい方法があることになる。
しかし、自作平衡二分木を使わないと配列をずらすのはむずかしい。

> 空の multiset があります
> 以下のクエリを処理した後の multiset を答えてください
> - $0$ を追加する
> - 小さい方から $K_i$ 個選び、$1$ 増やす

multiset 内は常に降順に並んでいると考えて、小さいほうから $K_i$ 個を選んで $1$ を足すと、値の境界はほとんど変わらないことがわかる。
そこで、 `std::multiset<int>` に値の境界を持たせて、
$i$ 番目に大きい境界から $i+1$ 番目に大きい境界までが $i$ である とすると、
$K_i$ 個を選んで $1$ を足すクエリが、境界を 1 つ追加・1 つずらす操作になって、 $O(N\log N)$ で解ける。

## 実装

63ms / 1000ms
https://oj.uz/submission/213054

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define all(a) begin(a), end(a)
#define each(i,a) for(auto&& i : a)
 
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<pii> a(n);
    each(i, a) cin >> i.first >> i.second;
    sort(all(a));
    multiset<int> X; // i 番目に大さい境界から i + 1 番目に大さい境界までが i である
    X.insert(0);
    each(i, a){
        auto [h, k] = i;
        X.insert(h);
        auto p = X.upper_bound(h - k), q = prev(p);
        int next = *q + *p - (h - k);
        if(q != X.begin()) X.erase(q);
        X.insert(next);
        X.erase(p);
    }
    ll ans = 0, cnt = 0;
    for(auto p = X.end(); p-- != X.begin(); cnt++) ans += cnt * *p;
    cout << ans << '\n';
}

## 感想

これって slope trick ってやつですか　なるほど