救援 [東京工業大学プログラミングコンテスト2019 H]

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_h

前提知識

• 動的構築セグメントツリー
• マージテク

解説

https://atcoder.jp/contests/ttpc2019/submissions/7238575

まずは簡単なことから考えていく。
条件を見ると支援関係は連結成分ごとに考えられていく。
ある連結成分で支援を行える額は総和をとっても問題ない。
支援を受ける額は、Pが大きい順に貪欲に割り当てれば最適っぽい。
クエリを見ていくと、全体の支援で救える人数の最大値は2つの連結成分を連結させる時に、
両方の連結成分での救える人数の最大値を引いて、新しくできた連結成分での救える人数の最大値を足せば、
インクリメンタルに答えを構築できる。
ここまではよくある方針。

両方の連結成分の最大値を引くのもメモっておけばいいいし、連結についてはUnionfindでいい。
問題が、新しく連結成分を作ったときの最適解をいかに求めるかという部分である。
何が簡単に求めるかという観点で探してみると、支援額の総額は簡単に求められる。
ここからがブレイクスルー。
支援を受ける国のPをindexとしたセグメントツリーを考える。
Pをindexとして、頂点には(Xの合計, X*Pの合計)を乗せる。
このセグメントツリーでXの合計＜支援額の総和をとなるPを二分探索で求める。
これでPを大きい淳に貪欲に割り当てるときの支援される上限まで支援されるPが特定できる。
あとは、境界になっている部分で残りの割り当てを行えばいい。

最後に連結成分ごとにセグメントツリーを管理する必要があり、連結させるときにマージする必要がある。
これは、マージテクを使おう。
マージテクを使えば、ならしで全体O(logN)が達成できる。

int N;
int X[101010], P[101010];
DynamicSegTree st[101010];
ll memo[101010];
vector<pair<ll, ll>> buf[101010];
ll tot[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> X[i] >> P[i];

    rep(i, 0, N) {
        if(0 <= X[i])
            tot[i] = X[i];
        else {
            buf[i].push_back({-X[i], P[i]});
            st[i].add(P[i], {-X[i], -1LL * X[i] * P[i]});
        }
    }

    ll ans = 0;
    int Q;
    cin >> Q;
    UnionFind uf(N);
    rep(q, 0, Q)
    {
        int a, b; cin >> a >> b;
        a--;
        b--;

        int aa = uf[a];
        int bb = uf[b];

        if(aa != bb) {
            ans -= memo[aa];
            ans -= memo[bb];

            if(buf[aa].size() > buf[bb].size())
                swap(aa, bb);

            // aaをbbにくっつける
            tot[bb] += tot[aa];
            fore(p, buf[aa]) {
                buf[bb].push_back(p);
                st[bb].add(p.second, {p.first, p.first * p.second});
            }

            uf(aa, bb);

            int ng = 0, ok = inf;
            while(ng + 1 != ok) {
                int md = (ng + ok) / 2;
                auto p = st[bb].get(md, inf);
                if(p.first < tot[bb])
                    ok = md;
                else
                    ng = md;
            }

            auto p = st[bb].get(ok, inf);
            memo[bb] = p.second;

            ll rest = tot[bb] - p.first;
            auto pp = st[bb].get(ng, ok);
            memo[bb] += min(rest, pp.first) * ng;
            ans += memo[bb];
        }

        printf("%lld\n", ans);
    }
}