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]]); }