#ifndef HIDDEN_IN_VS // 折りたたみ用 // 警告の抑制 #define _CRT_SECURE_NO_WARNINGS // ライブラリの読み込み #include using namespace std; // 型名の短縮 using ll = long long; // -2^63 ~ 2^63 = 9 * 10^18(int は -2^31 ~ 2^31 = 2 * 10^9) using pii = pair; using pll = pair; using pil = pair; using pli = pair; using vi = vector; using vvi = vector; using vvvi = vector; using vl = vector; using vvl = vector; using vvvl = vector; using vb = vector; using vvb = vector; using vvvb = vector; using vc = vector; using vvc = vector; using vvvc = vector; using vd = vector; using vvd = vector; using vvvd = vector; template using priority_queue_rev = priority_queue, greater>; using Graph = vvi; // 定数の定義 const double PI = acos(-1); const vi DX = { 1, 0, -1, 0 }; // 4 近傍(下,右,上,左) const vi DY = { 0, 1, 0, -1 }; int INF = 1001001001; ll INFL = 4004004004004004004LL; double EPS = 1e-15; // 入出力高速化 struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp; // 汎用マクロの定義 #define all(a) (a).begin(), (a).end() #define sz(x) ((int)(x).size()) #define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), x)) #define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), x)) #define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");} #define YES(b) {cout << ((b) ? "YES\n" : "NO\n");} #define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順 #define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順 #define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順 #define repe(v, a) for(const auto& v : (a)) // a の全要素(変更不可能) #define repea(v, a) for(auto& v : (a)) // a の全要素(変更可能) #define repb(set, d) for(int set = 0; set < (1 << int(d)); ++set) // d ビット全探索(昇順) #define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て(昇順) #define smod(n, m) ((((n) % (m)) + (m)) % (m)) // 非負mod #define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去 #define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了 // 汎用関数の定義 template inline ll pow(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; } template inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新(更新されたら true を返す) template inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新(更新されたら true を返す) template inline T get(T set, int i) { return (set >> i) & T(1); } // 演算子オーバーロード template inline istream& operator>>(istream& is, pair& p) { is >> p.first >> p.second; return is; } template inline istream& operator>>(istream& is, vector& v) { repea(x, v) is >> x; return is; } template inline vector& operator--(vector& v) { repea(x, v) --x; return v; } template inline vector& operator++(vector& v) { repea(x, v) ++x; return v; } #endif // 折りたたみ用 #if __has_include() #include using namespace atcoder; #ifdef _MSC_VER #include "localACL.hpp" #endif //using mint = modint1000000007; using mint = modint998244353; //using mint = modint; // mint::set_mod(m); namespace atcoder { inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; } inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; } } using vm = vector; using vvm = vector; using vvvm = vector; #endif #ifdef _MSC_VER // 手元環境(Visual Studio) #include "local.hpp" #else // 提出用(gcc) inline int popcount(int n) { return __builtin_popcount(n); } inline int popcount(ll n) { return __builtin_popcountll(n); } inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : -1; } inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : -1; } inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; } inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; } #define gcd __gcd #define dump(...) #define dumpel(v) #define dump_list(v) #define dump_mat(v) #define input_from_file(f) #define output_to_file(f) #define Assert(b) { if (!(b)) while (1) cout << "OLE"; } #endif //【Implicit Treap(M-可換モノイド)】 /* * Implicit_treap() : O(1) * 空で初期化する. * 要素は左作用付き可換モノイド (S, op, e, F, act, comp, id) の元とする. * * Implicit_treap(vS a) : O(n log n) * 配列 a[0..n) で初期化する. * * bool empty() : O(1) * 空かを返す. * * int size() : O(1) * 要素数を返す. * * S get(int i) : O(log n) * a[i] を返す(なければ e() を返す) * * S prod(int l, int r) : O(log n) * Σa[l..r) を返す(空なら e() を返す) * * apply(int i, F f) : O(log n) * a[i] = f( a[i] ) とする. * * apply(int l, int r, F f) : O(log n) * a[l..r) = f( a[l..r) ) とする(空なら何もしない) * * int max_right(int l, function g) : O(log n) * g( Σa[l..r) ) = true となる最大の r を返す. * 制約:g( e() ) = true かつ g は単調 * * int min_left(int r, function g) : O(log n) * g( Σa[l..r) ) = true となる最小の l を返す. * 制約:g( e() ) = true かつ g は単調 * * insert(int i, S x) : O(log n) * a[i] = x を挿入する(元々あった要素は右に移動する) * * erase(int i) : O(log n) * a[i] の要素を削除し左詰めする(なければ何もしない) * * reverse(int l, int r) : O(log n) * a[l..r) を左右反転する. * * rotate(int l, int m, int r) : O(log n) * a[l, r) を,a[m] が先頭にくるよう巡回シフトする. * * Implicit_treap split(int key) : O(log n) * 自身から位置 key 以上の要素を切り出し,切り出して出来た木を返す. * * void merge(Implicit_treap IT) : O(log n) * 自身の右側に IT をマージする. * * vS get_all() : O(n) * 全要素のリストを返す. */ template class Implicit_treap { // 参考 : https://xuzijian629.hatenablog.com/entry/2018/12/08/000452 inline static bool first_call = true; inline static mt19937 rnd; struct Node { S value; // 頂点の値 S acc; // 部分木のノードの総 op F lazy; // 部分木のノードへの遅延作用 unsigned int priority; // ランダムに決めた優先度 int cnt; // 部分木のノード数 bool rev; // 部分木が反転されているか Node* l, * r; // 左右の子へのポインタ Node(S value, unsigned int priority) : value(value), acc(e()), lazy(id()), priority(priority), cnt(1), rev(false), l(nullptr), r(nullptr) {} }; Node* root; // 部分木 t のノード数を返す. int cnt(Node* t) { return t ? t->cnt : 0; } // op(部分木 t) を返す. S acc(Node* t) { return t ? t->acc : e(); } // 部分木 t のノード数を更新する. void update_cnt(Node* t) { if (t) t->cnt = cnt(t->l) + 1 + cnt(t->r); } // op(部分木 t) を更新する. void update_acc(Node* t) { if (t) t->acc = op(acc(t->l), op(t->value, acc(t->r))); } // 部分木 t の cnt と acc を更新する(子は更新済であること) void pushup(Node* t) { update_cnt(t); update_acc(t); } // 遅延評価を適用する. void pushdown(Node* t) { // 部分木 t の反転フラグが true なら,実際に反転させた上で反転フラグを false にする. if (t && t->rev) { t->rev = false; swap(t->l, t->r); // t の子については反転フラグを flip しておくだけにする. if (t->l) t->l->rev ^= 1; if (t->r) t->r->rev ^= 1; } // 部分木 t に作用が溜まっていたら,実際に作用させた上で作用を id() にする. if (t && t->lazy != id()) { // t の子については作用を遅延させておくだけにする(acc だけは更新する) if (t->l) { t->l->lazy = comp(t->lazy, t->l->lazy); t->l->acc = act(t->lazy, t->l->acc); } if (t->r) { t->r->lazy = comp(t->lazy, t->r->lazy); t->r->acc = act(t->lazy, t->r->acc); } t->value = act(t->lazy, t->value); t->lazy = id(); } // 部分木 t の cnt と acc を更新する. pushup(t); } // 部分木 t を位置 key 未満[以上] に分割し,それぞれの根へのポインタを l[ r ] に格納する. void split(Node* t, int key, Node*& l, Node*& r) { // 空なら分割しなくていい. if (!t) { l = r = nullptr; return; } // t の情報を更新する. pushdown(t); // 部分木 t 内の自身の位置を得る. int implicit_key = cnt(t->l); if (key <= implicit_key) { // 左の木を分割しその左側を l に採用する.小さくなった右側は t->l に繋ぎ直す. split(t->l, key, l, t->l); r = t; } else { // 右の木を分割しその右側を r に採用する.小さくなった左側は t->r に繋ぎ直す. split(t->r, key - implicit_key - 1, t->r, r); l = t; } // 繋ぎ変えで部分木 t の cnt と acc が壊れたので更新する. pushup(t); } // 部分木 l, r をこの順にマージした部分木を t に格納する. void merge(Node*& t, Node* l, Node* r) { // l, r の情報を更新する. pushdown(l); pushdown(r); // 片方が空ならもう一方を根とすればよい. if (!l) t = r; else if (!r) t = l; // 優先度が高い方を根とし,もう一方をその子とマージする. else if (l->priority > r->priority) { merge(l->r, l->r, r); t = l; } else { merge(r->l, l, r->l); t = r; } // 部分木 t の cnt と acc を更新する. pushup(t); } int max_right(Node* t, S x, int offset, const function& g) { if (!t) return offset; // t の情報を更新する. pushdown(t); // 左の子の中に答えがあるなら左の子へ if (t->l) { S nx = op(x, t->l->acc); if (!g(nx)) return max_right(t->l, x, offset, g); x = nx; } // 自身が答えならそれを返す. S nx = op(x, t->value); if (!g(nx)) return offset + cnt(t->l); x = nx; // 右の子の中に答えがあるなら右の子へ if (t->r) { S nx = op(x, t->r->acc); if (!g(nx)) return max_right(t->r, x, offset + cnt(t->l) + 1, g); x = nx; } // どこにもないなら右端を返す. return offset + cnt(t->l) + 1 + cnt(t->r); } int min_left(Node* t, S x, int offset, const function& g) { if (!t) return offset; // t の情報を更新する. pushdown(t); // 右の子の中に答えがあるなら右の子へ if (t->r) { S nx = op(t->r->acc, x); if (!g(nx)) return min_left(t->r, x, offset + cnt(t->l) + 1, g); x = nx; } // 自身が答えならそれを返す. S nx = op(t->value, x); if (!g(nx)) return offset + cnt(t->l); x = nx; // 左の子の中に答えがあるなら左の子へ if (t->l) { S nx = op(t->l->acc, x); if (!g(nx)) return min_left(t->l, x, offset, g); x = nx; } // どこにもないなら左端を返す. return offset; } void get_all(Node* t, vector& seq) { if (!t) return; pushdown(t); get_all(t->l, seq); seq.emplace_back(t->value); get_all(t->r, seq); } public: // 空で初期化する. Implicit_treap() : root(nullptr) { // verify : https://www.spoj.com/problems/IITWPC4D/ if (Implicit_treap::first_call) { rnd = mt19937((int)time(NULL)); Implicit_treap::first_call = false; } } // 配列 a[0..n) で初期化する. Implicit_treap(const vector& a) : root(nullptr) { // verify : https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum if (Implicit_treap::first_call) { rnd = mt19937((int)time(NULL)); Implicit_treap::first_call = false; } rep(i, sz(a)) insert(i, a[i]); } // 要素が空かを返す. bool empty() { return !(bool)root; } // 要素数を返す. int size() { // verify : https://www.spoj.com/problems/IITWPC4D/ return cnt(root); } // a[l..r) = f( a[l..r) ) とする(空なら何もしない) void apply(int l, int r, F f) { // verify : https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum if (l >= r) return; Node* lt, * mt, * rt; // [l..r) に対応する部分木 mt を切り出してくる. split(root, l, lt, rt); split(rt, r - l, mt, rt); // mt への作用 f を遅延させる(acc だけは更新する) if (mt) { mt->lazy = comp(f, mt->lazy); mt->acc = act(f, mt->acc); } // 木を元に戻しておく. merge(rt, mt, rt); merge(root, lt, rt); } // a[i] = f( a[i] ) とする(なければ何もしない) void apply(int i, F f) { apply(i, i + 1, f); } // op( a[l..r) ) を返す(空なら e() を返す) S prod(int l, int r) { // verify : https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum if (l >= r) return e(); Node* lt, * mt, * rt; // [l..r) に対応する部分木 mt を切り出してくる. split(root, l, lt, rt); split(rt, r - l, mt, rt); // 値は既に acc に格納されている. S res = acc(mt); // 木を元に戻しておく. merge(rt, mt, rt); merge(root, lt, rt); return res; } // a[i] を返す(なければ e() を返す) S get(int i) { // verify : https://www.spoj.com/problems/IITWPC4D/ return prod(i, i + 1); } // g( op( a[l..r) ) ) = true となる最大の r を返す. int max_right(int l, const function& g) { // verify : https://atcoder.jp/contests/practice2/tasks/practice2_j Node* lt, * rt; // [l..n) に対応する部分木 rt を切り出してくる. split(root, l, lt, rt); S x = e(); int res = max_right(rt, x, l, g); // 木を元に戻しておく. merge(root, lt, rt); return res; } // g( op( a[l..r) ) ) = true となる最小の l を返す. int min_left(int r, const function& g) { Node* lt, * rt; // [0..r) に対応する部分木 lt を切り出してくる. split(root, r, lt, rt); S x = e(); int res = min_left(lt, x, 0, g); // 木を元に戻しておく. merge(root, lt, rt); return res; } // a[i] = x を挿入する(元々あった要素は右に移動する) void insert(int i, S x) { // verify : https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum Node* lt, * rt; // 一旦 i で分割し,x を挟んでからマージする. split(root, i, lt, rt); merge(lt, lt, new Node(x, rnd())); merge(root, lt, rt); } // a[i] の要素を削除し左詰めする(なければ何もしない) void erase(int i) { // verify : https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum Node* lt, * mt, * rt; // i の前後で分割し,i だけ除いてマージする. split(root, i + 1, lt, rt); split(lt, i, lt, mt); merge(root, lt, rt); } // a[l..r) を左右反転する. void reverse(int l, int r) { // verify : https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum if (l >= r) return; Node* lt, * mt, * rt; // [l..r) に対応する部分木 mt を切り出してくる. split(root, l, lt, rt); split(rt, r - l, mt, rt); // 反転フラグを flip する. mt->rev ^= 1; // 木を元に戻しておく. merge(rt, mt, rt); merge(root, lt, rt); } // a[l, r) を,a[m] が先頭にくるよう巡回シフトする. void rotate(int l, int m, int r) { // verify : https://onlinejudge.u-aizu.ac.jp/problems/1508 // 全体を反転 reverse(l, r); // 左右それぞれを反転 reverse(l, l + r - m); reverse(l + r - m, r); } // 自身から位置 key 以上の要素を切り出し,切り出して出来た木を返す. Implicit_treap split(int key) { // verify : https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum Node* l, * r; split(root, key, l, r); root = l; Implicit_treap ret; ret.root = r; return ret; } // 自身の右側に IT をマージする. void merge(Implicit_treap& IT) { // verify : https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum merge(root, root, IT.root); } // 全要素のリストを返す. vector get_all() { // verify : https://www.spoj.com/problems/TWIST/ vector seq; get_all(root, seq); return seq; } #ifdef _MSC_VER friend ostream& operator<<(ostream& os, Implicit_treap IT) { os << IT.get_all(); return os; } #endif }; //【区間和の最大値 モノイド】(の改変) /* * S ∋ f = {fl, fr, fa, fs} : f に対応する区間についての以下の値を表す: * fl[fr] : 左[右]端を含む区間和の最大値 * fa : 任意の区間和の最大値 * fs : 総和 * f op g : f, g に対応する区間をこの順に繋げた区間を表す. */ // 参考 : https://hotman78.hatenablog.com/entry/2020/06/17/102519 // verify : https://yukicoder.me/problems/no/2223 using T115 = ll; using S115 = tuple; // (左端を含む, 右端を含む, 任意, 総和, 幅) S115 op115(S115 f, S115 g) { auto [fl, fr, fa, fs, fw] = f; auto [gl, gr, ga, gs, gw] = g; T115 hl = max(fl, fs + gl); T115 hr = max(gr, fr + gs); T115 ha = max({ fa, ga, fr + gl }); T115 hs = fs + gs; ll hw = fw + gw; return { hl, hr, ha, hs, hw }; } S115 e115() { return { -INFL, -INFL, -INFL, 0, 0 }; } using F115 = bool; S115 act115(F115 f, S115 x) { return x; } F115 comp115(F115 f, F115 g) { return f; } F115 id115() { return 0; } #define RangeSumMax_monoid2 S115, op115, e115, F115, act115, comp115, id115 void WA_TLE_RE() { int n; cin >> n; Implicit_treap IT; rep(i, n) { ll a, b; cin >> a >> b; IT.insert(i, { a * b, a * b, a * b, a * b, b }); } dump(IT); int q; cin >> q; rep(hoge, q) { int tp; cin >> tp; if (tp == 1) { ll x, y; cin >> x >> y; x--; function g = [&](S115 s) { return get<4>(s) <= x; }; int i = IT.max_right(0, g); auto [fl, fr, fa, fs, fw] = IT.prod(0, i); auto [gl, gr, ga, gs, gw] = IT.get(i); ll a = gs / gw; IT.erase(i); if (fw + gw - 1 - x > 0) { ll b = fw + gw - 1 - x; IT.insert(i, { a * b, a * b, a * b, a * b, b }); } IT.insert(i, { y, y, y, y, 1 }); if (x - fw > 0) { ll b = x - fw; IT.insert(i, { a * b, a * b, a * b, a * b, b }); } } else { ll l, r; cin >> l >> r; l--; function g1 = [&](S115 s) { return get<4>(s) <= l; }; int i1 = IT.max_right(0, g1); auto [fl1, fr1, fa1, fs1, fw1] = IT.prod(0, i1); auto [gl1, gr1, ga1, gs1, gw1] = IT.get(i1); ll a1 = gs1 / gw1; IT.erase(i1); if (fw1 + gw1 - l > 0) { ll b = fw1 + gw1 - l; IT.insert(i1, { a1 * b, a1 * b, a1 * b, a1 * b, b }); } if (l - fw1 > 0) { ll b = l - fw1; IT.insert(i1, { a1 * b, a1 * b, a1 * b, a1 * b, b }); i1++; } function g2 = [&](S115 s) { return get<4>(s) <= r; }; int i2 = IT.max_right(0, g2); if (i2 != IT.size()) { auto [fl2, fr2, fa2, fs2, fw2] = IT.prod(0, i2); auto [gl2, gr2, ga2, gs2, gw2] = IT.get(i2); ll a2 = gs2 / gw2; IT.erase(i2); if (fw2 + gw2 - r > 0) { ll b = fw2 + gw2 - r; IT.insert(i2, { a2 * b, a2 * b, a2 * b, a2 * b, b }); } if (r - fw2 > 0) { ll b = r - fw2; IT.insert(i2, { a2 * b, a2 * b, a2 * b, a2 * b, b }); } } dump(i1, i2); auto [fl, fr, fa, fs, fw] = IT.prod(i1, i2); if (fa < 0) fa /= fw; cout << fa << endl; } dump(IT); } } //【区間和の最大値 モノイド】 /* * S ∋ f = {fl, fr, fa, fs} : f に対応する区間についての以下の値を表す: * fl[fr] : 左[右]端を含む区間和の最大値 * fa : 任意の区間和の最大値 * fs : 総和 * f op g : f, g に対応する区間をこの順に繋げた区間を表す. */ // 参考 : https://hotman78.hatenablog.com/entry/2020/06/17/102519 // verify : https://yukicoder.me/problems/no/2223 using T028 = ll; using S028 = tuple; // (左端を含む, 右端を含む, 任意, 総和) S028 op028(S028 f, S028 g) { auto [fl, fr, fa, fs] = f; auto [gl, gr, ga, gs] = g; T028 hl = max(fl, fs + gl); T028 hr = max(gr, fr + gs); T028 ha = max({ fa, ga, fr + gl }); T028 hs = fs + gs; return { hl, hr, ha, hs }; } S028 e028() { return { -INFL, -INFL, -INFL, 0 }; } #define RangeSumMax_monoid S028, op028, e028 int main() { int n; cin >> n; vl a(n), b(n); rep(i, n) cin >> a[i] >> b[i]; vl b_acc(n + 1); rep(i, n) b_acc[i + 1] = b_acc[i] + b[i]; vl xs; repi(i, 0, n) xs.push_back(b_acc[i]); int q; cin >> q; vector> qs(n); rep(j, q) { int tp; ll q1, q2; cin >> tp >> q1 >> q2; if (tp == 1) { xs.push_back(q1 - 1); xs.push_back(q1); } else { xs.push_back(q1 - 1); xs.push_back(q2); } qs[j] = { tp, q1, q2 }; } uniq(xs); int m = sz(xs) - 1; dump(xs); vector ini(m); int pt = 0; rep(j, m) { ll w = xs[j + 1] - xs[j]; ll c = a[pt]; if (c > 0) ini[j] = { c * w, c * w, c * w, c * w }; else ini[j] = { c, c, c, c * w };; if (xs[j + 1] == b_acc[pt + 1]) pt++; } segtree seg(ini); dump(seg); rep(j, q) { auto [tp, q1, q2] = qs[j]; if (tp == 1) { ll x = q1 - 1, y = q2; int i = lbpos(xs, x); seg.set(i, { y, y, y, y }); } else { ll l = q1 - 1, r = q2; int il = lbpos(xs, l); int ir = lbpos(xs, r); auto [fl, fr, fa, fs] = seg.prod(il, ir); cout << fa << endl; } } }