Filters [AtCoder Beginner Contest 196 E]

https://atcoder.jp/contests/abc196/tasks/abc196_e

解説

https://atcoder.jp/contests/abc196/submissions/21120300 公式解説では関数合成を行うやり方が紹介されている。
関数合成か…よくわかってないのよね…
半環問題でやったことはあるけど…
ということで、別解を紹介する。

公式解説の方が実装も少ないが、やや数学要素が強いので実装で頑張るやり方を紹介する。
「実装を頑張る」方針でやっているので、興味本位で聞いた方がいいかもしれない。

まとめながら処理していく

各クエリ毎に別々に処理するのではなく、まとめて処理していく。

処理1

t[i]=1の場合は、すべてのクエリに数値を足していく処理になるので、それぞれ足すのではなく
deltaという変数を用意して、そちらに足し合わせていくことにする。
評価するときにX[i]ではなくX[i]+deltaで評価すれば、つじつまがある。

処理2

t[i]=2の場合は、maxを取っていくが、これは一気にできないので、工夫する必要がある。
例えば、

1 3 5 7

となって、max(x,6)とした場合は

6 6 6 7

に変化する。これ以降の操作で6はまとめて考えても問題無い。
つまり状態が

6 7

に圧縮されたと考えることができる。

この辺の工夫を考慮すると、配列Xをあらかじめソートしておき、小さい方から順番にmaxを処理していくことにする。
すると、maxによる更新が走る毎に要素が1つ減るということになる。
例えば、

1 3 5 7

の場合、1を見て更新、3を見て更新、5を見て更新、7を見てダメなので打ち切り（それ以降は必要ない）
こうすると、4回更新しているが、それ以降は6 7と圧縮されるので、
回数が多くなると、その分それ以降考慮すべき要素が減るため、計算量をならしで考えると問題ない。
かなり冗長な表現になってしまったが、ならしで間に合う系は慣れるしかない。

まとめてしまっても最後には復元する必要があるので、UnionFindを使って、どれとどれが同じであるかを
管理しながらマージしていく。

処理3

これは処理2とほぼ同じ。
ソートして大きい順から順番にmaxを処理していく。

実装

処理2,3をするために前後から1つずつ取って判定して、入れなおすことをしたいのでdequeを使う。
最初、UnionFindの代わりにマージテクを使って管理していたが、TLEしたのでUnionFindにした。
実装見てもらえば分かるが、結構しんどい。

int N, A[201010], T[201010];
int Q, X[201010];
deque<pair<ll, int>> que;
//---------------------------------------------------------------------------------------------------
void makeInitialQue() {
    vector<pair<int, int>> v;
    rep(i, 0, Q) v.push_back({ X[i], i });
    sort(all(v));
    fore(p, v) que.push_back({ p.first, p.second });
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i] >> T[i];
    cin >> Q;
    rep(i, 0, Q) cin >> X[i];

    makeInitialQue();

    UnionFind uf(Q);

    ll delta = 0;
    rep(i, 0, N) {
        if (T[i] == 1) delta += A[i];
        else if (T[i] == 2) {
            int top = -1;
            while (!que.empty()) {
                auto p = que.front();
                if (p.first + delta <= A[i]) {
                    if (top < 0) top = p.second;
                    else uf(top, p.second);
                    que.pop_front();
                }
                else break;
            }
            if (0 <= top) que.push_front({ A[i] - delta, uf[top] });
        }
        else if (T[i] == 3) {
            int top = -1;
            while (!que.empty()) {
                auto p = que.back();
                if (A[i] <= p.first + delta) {
                    if (top < 0) top = p.second;
                    else uf(top, p.second);
                    que.pop_back();
                }
                else break;
            }
            if (0 <= top) que.push_back({ A[i] - delta, uf[top] });
        }
    }

    map<int, ll> mp;
    while (!que.empty()) {
        auto p = que.front();
        mp[uf[p.second]] = p.first + delta;
        que.pop_front();
    }

    rep(i, 0, Q) printf("%lld\n", mp[uf[i]]);
}