DOJ Beginner Contest 13 F - Advance
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 13
- 問題
- F - Advance
個の地域があり、軍隊が地域 を通るときは、まず兵士 人を守備隊として残し(その直後に 人以上残っていなければなりません)、そのあと兵士 人が合流します。次の 2 種類のクエリを 個処理する問題です(、)。
1 i a b: を に、 を に変える。2 l r:地域 を順に通るとき、地域 に入る時点で必要な兵士の最小人数を答える。
区間を通る過程を「入るときに必要な最小人数 」と「ちょうど 人で入ったときに出ていく人数 」の組 で表します。 人より多く入れば、その分だけ出ていく人数も増えるので、この 2 つで区間の通り方が決まります。
地域 1 つだけなら、 人を残したあとに 人以上必要なので で、そのとき です。
区間 を通ったあとに区間 を通るとき、つなげた区間の組は次のようになります。
- のとき: 人で入れば 2 つ目の区間にも入れるので、。
- のとき:2 つ目の区間に入るのに 人足りないので、最初にその分多く入る必要があり、。
この演算は結合的です(区間をつなげる順によらず、実際に通ったときの結果を表しているため)。単位元は です。よってセグメント木に載せれば、クエリ 1 は 1 点の更新、クエリ 2 は区間の積の で、それぞれ で処理できます。
値は最大で 程度なので、64 bit 整数で足ります。
C++
#include "shogo-library/base/all"#include "shogo-library/data_structures/segtree.hpp"
struct M { using S = pl; S op(const S &l, const S &r) const { if (l.second >= r.first) { return {l.first, l.second - r.first + r.second}; } else { return {l.first + r.first - l.second, r.second}; } } S e() const { return {0, 0}; }};
void solve() { LL(N, Q); vec<M::S> init; init.reserve(N); rep(i, N) { LL(a, b); init.push_back({b + 1, a + 1}); } SegTree<M> seg(init); rep(Q) { LL(q); if (q == 1) { LL(i, a, b); seg.set(i - 1, {b + 1, a + 1}); } else { LL(l, r); print(seg.prod(l - 1, r).first); } }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}SegTree<M> は、モノイド M の演算 op と単位元 e を使うセグメント木です。要素の first が (必要な最小人数)、second が (出ていく人数)です。
使用ライブラリ:cpp_include@4b58304