コンテンツにスキップ

DOJ Beginner Contest 13 F - Advance

サイト
DOJ
コンテスト
DOJ Beginner Contest 13
問題
F - Advance

NN 個の地域があり、軍隊が地域 ii を通るときは、まず兵士 BiB_i 人を守備隊として残し(その直後に 11 人以上残っていなければなりません)、そのあと兵士 AiA_i 人が合流します。次の 2 種類のクエリを QQ 個処理する問題です(1≤N,Q≤2000001 \le N, Q \le 200000、0≤Ai,Bi≤1090 \le A_i, B_i \le 10^9)。

  • 1 i a b:AiA_i を aa に、BiB_i を bb に変える。
  • 2 l r:地域 l,l+1,…,rl, l+1, \dots, r を順に通るとき、地域 ll に入る時点で必要な兵士の最小人数を答える。

区間を通る過程を「入るときに必要な最小人数 xx」と「ちょうど xx 人で入ったときに出ていく人数 yy」の組 (x,y)(x, y) で表します。xx 人より多く入れば、その分だけ出ていく人数も増えるので、この 2 つで区間の通り方が決まります。

地域 ii 1 つだけなら、BiB_i 人を残したあとに 11 人以上必要なので x=Bi+1x = B_i + 1 で、そのとき y=Ai+1y = A_i + 1 です。

区間 (x1,y1)(x_1, y_1) を通ったあとに区間 (x2,y2)(x_2, y_2) を通るとき、つなげた区間の組は次のようになります。

  • y1≥x2y_1 \ge x_2 のとき:x1x_1 人で入れば 2 つ目の区間にも入れるので、(x1, y1−x2+y2)(x_1, \ y_1 - x_2 + y_2)。
  • y1<x2y_1 < x_2 のとき:2 つ目の区間に入るのに x2−y1x_2 - y_1 人足りないので、最初にその分多く入る必要があり、(x1+x2−y1, y2)(x_1 + x_2 - y_1, \ y_2)。

この演算は結合的です(区間をつなげる順によらず、実際に通ったときの結果を表しているため)。単位元は (0,0)(0, 0) です。よってセグメント木に載せれば、クエリ 1 は 1 点の更新、クエリ 2 は区間の積の xx で、それぞれ O(log⁡N)O(\log N) で処理できます。

値は最大で (109+1)×200000≈2×1014(10^9 + 1) \times 200000 \approx 2 \times 10^{14} 程度なので、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 が xx(必要な最小人数)、second が yy(出ていく人数)です。

使用ライブラリ:cpp_include@4b58304