結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 2025-09-06 15:34:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,209 ms / 2,500 ms |
コード長 | 17,362 bytes |
コンパイル時間 | 2,397 ms |
コンパイル使用メモリ | 209,476 KB |
実行使用メモリ | 27,960 KB |
最終ジャッジ日時 | 2025-09-06 15:35:28 |
合計ジャッジ時間 | 31,745 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
/* Original Python code: (import typing) def _ceil_pow2(n: int) -> int: x = 0 while (1 << x) < n: x += 1 return x def _bsf(n: int) -> int: x = 0 while n % 2 == 0: x += 1 n //= 2 return x class LazySegTree: def __init__( self, op: typing.Callable[[typing.Any, typing.Any], typing.Any], e: typing.Any, mapping: typing.Callable[[typing.Any, typing.Any], typing.Any], composition: typing.Callable[[typing.Any, typing.Any], typing.Any], id_: typing.Any, v: typing.Union[int, typing.List[typing.Any]]) -> None: self._op = op self._e = e self._mapping = mapping self._composition = composition self._id = id_ if isinstance(v, int): v = [e] * v self._n = len(v) self._log = _ceil_pow2(self._n) self._size = 1 << self._log self._d = [e] * (2 * self._size) self._lz = [self._id] * self._size for i in range(self._n): self._d[self._size + i] = v[i] for i in range(self._size - 1, 0, -1): self._update(i) def set(self, p: int, x: typing.Any) -> None: assert 0 <= p < self._n p += self._size for i in range(self._log, 0, -1): self._push(p >> i) self._d[p] = x for i in range(1, self._log + 1): self._update(p >> i) def get(self, p: int) -> typing.Any: assert 0 <= p < self._n p += self._size for i in range(self._log, 0, -1): self._push(p >> i) return self._d[p] def prod(self, left: int, right: int) -> typing.Any: assert 0 <= left <= right <= self._n if left == right: return self._e left += self._size right += self._size for i in range(self._log, 0, -1): if ((left >> i) << i) != left: self._push(left >> i) if ((right >> i) << i) != right: self._push((right - 1) >> i) sml = self._e smr = self._e while left < right: if left & 1: sml = self._op(sml, self._d[left]) left += 1 if right & 1: right -= 1 smr = self._op(self._d[right], smr) left >>= 1 right >>= 1 return self._op(sml, smr) def all_prod(self) -> typing.Any: return self._d[1] def apply(self, left: int, right: typing.Optional[int] = None, f: typing.Optional[typing.Any] = None) -> None: assert f is not None if right is None: p = left assert 0 <= left < self._n p += self._size for i in range(self._log, 0, -1): self._push(p >> i) self._d[p] = self._mapping(f, self._d[p]) for i in range(1, self._log + 1): self._update(p >> i) else: assert 0 <= left <= right <= self._n if left == right: return left += self._size right += self._size for i in range(self._log, 0, -1): if ((left >> i) << i) != left: self._push(left >> i) if ((right >> i) << i) != right: self._push((right - 1) >> i) l2 = left r2 = right while left < right: if left & 1: self._all_apply(left, f) left += 1 if right & 1: right -= 1 self._all_apply(right, f) left >>= 1 right >>= 1 left = l2 right = r2 for i in range(1, self._log + 1): if ((left >> i) << i) != left: self._update(left >> i) if ((right >> i) << i) != right: self._update((right - 1) >> i) def max_right( self, left: int, g: typing.Callable[[typing.Any], bool]) -> int: assert 0 <= left <= self._n assert g(self._e) if left == self._n: return self._n left += self._size for i in range(self._log, 0, -1): self._push(left >> i) sm = self._e first = True while first or (left & -left) != left: first = False while left % 2 == 0: left >>= 1 if not g(self._op(sm, self._d[left])): while left < self._size: self._push(left) left *= 2 if g(self._op(sm, self._d[left])): sm = self._op(sm, self._d[left]) left += 1 return left - self._size sm = self._op(sm, self._d[left]) left += 1 return self._n def min_left(self, right: int, g: typing.Any) -> int: assert 0 <= right <= self._n assert g(self._e) if right == 0: return 0 right += self._size for i in range(self._log, 0, -1): self._push((right - 1) >> i) sm = self._e first = True while first or (right & -right) != right: first = False right -= 1 while right > 1 and right % 2: right >>= 1 if not g(self._op(self._d[right], sm)): while right < self._size: self._push(right) right = 2 * right + 1 if g(self._op(self._d[right], sm)): sm = self._op(self._d[right], sm) right -= 1 return right + 1 - self._size sm = self._op(self._d[right], sm) return 0 def _update(self, k: int) -> None: self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1]) def _all_apply(self, k: int, f: typing.Any) -> None: self._d[k] = self._mapping(f, self._d[k]) if k < self._size: self._lz[k] = self._composition(f, self._lz[k]) def _push(self, k: int) -> None: self._all_apply(2 * k, self._lz[k]) self._all_apply(2 * k + 1, self._lz[k]) self._lz[k] = self._id N,M = list(map(int,input().split())) iwai = [] for i in range(N): a,l,r = list(map(int,input().split())) l -= 1 iwai.append((i,a,l,r)) def op(x,y): return (x[0]+y[0],x[1]+y[1]) def mapping(f,x): return (f[0]+x[0],f[1]+x[1]) def comp(f,g): return (f[0]+g[0],f[1]+g[1]) id_ = (0,0) T = LazySegTree(op,(0,0),mapping,comp,id_,[(0,0) for _ in range(M)]) TT = LazySegTree(lambda x,y:x+y,0,lambda f,x:f+x,lambda f,g:f+g,0,[0 for _ in range(M)]) for _,a,l,r in iwai: T.apply(l,r,(a,1)) for i,a,l,r in iwai: TT.set(i,a) ans = 0 for _,a,l,r in iwai: ans += a*(r-l) - TT.prod(l,r) Q = int(input()) for _ in range(Q): x,y,u,v = list(map(int,input().split())) x -= 1;y -= 1;u -= 1 now,a,l,r = iwai[x] iwai[x] = (y,a,u,v) # まわりからの影響 T.apply(l,r,(-a,-1)) value,num = T.get(now) ans += a*num # 元いた場所の自分の影響 value = TT.prod(l,r) ans -= a*(r-l) - value TT.apply(now,now+1,-a) # 新転地の自分の影響 TT.apply(y,y+1,a) ans += a*(v-u) - TT.prod(u,v) # 新転地の周りの影響 value,num = T.prod(y,y+1) ans += -a*num T.apply(u,v,(a,1)) print(ans) #print("T :",*[T.get(i) for i in range(M)]) #print("TT :",*[TT.get(i) for i in range(M)]) */ #include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll,ll>; // Lazy segment tree specialized for pair<ll,ll> with range-add of pairs struct LazySegPair { int n; // original length int _log; int size; // size = 1<<_log vector<pll> d; // segment values vector<pll> lz; // lazy values for internal nodes, size 'size' pll e = {0,0}; pll id = {0,0}; static int ceil_pow2(int n) { int x = 0; while ((1 << x) < n) ++x; return x; } LazySegPair(int n_, const pll &e_ = {0,0}, const pll &id_ = {0,0}) { n = n_; e = e_; id = id_; if (n == 0) { _log = 0; size = 1; } else { _log = ceil_pow2(n); size = 1 << _log; } d.assign(2*size, e); lz.assign(size, id); } // initialize from vector LazySegPair(const vector<pll> &v, const pll &e_ = {0,0}, const pll &id_ = {0,0}) { n = (int)v.size(); e = e_; id = id_; _log = ceil_pow2(n); size = 1 << _log; d.assign(2*size, e); lz.assign(size, id); for (int i = 0; i < n; ++i) d[size + i] = v[i]; for (int i = size - 1; i >= 1; --i) _update(i); } inline pll op(const pll &x, const pll &y) { return pll{x.first + y.first, x.second + y.second}; } inline pll mapping(const pll &f, const pll &x) { return pll{f.first + x.first, f.second + x.second}; } inline pll composition(const pll &f, const pll &g) { return pll{f.first + g.first, f.second + g.second}; } void _update(int k) { d[k] = op(d[2*k], d[2*k+1]); } void _all_apply(int k, const pll &f) { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void _push(int k) { _all_apply(2*k, lz[k]); _all_apply(2*k+1, lz[k]); lz[k] = id; } void set(int p, const pll &x) { // assert 0 <= p < n int pp = p + size; for (int i = _log; i >= 1; --i) _push(pp >> i); d[pp] = x; for (int i = 1; i <= _log; ++i) _update(pp >> i); } pll get(int p) { int pp = p + size; for (int i = _log; i >= 1; --i) _push(pp >> i); return d[pp]; } // product on [l, r) pll prod(int l, int r) { // assert 0 <= l <= r <= n if (l == r) return e; int left = l + size; int right = r + size; for (int i = _log; i >= 1; --i) { if (((left >> i) << i) != left) _push(left >> i); if (((right >> i) << i) != right) _push((right - 1) >> i); } pll sml = e, smr = e; while (left < right) { if (left & 1) { sml = op(sml, d[left]); ++left; } if (right & 1) { --right; smr = op(d[right], smr); } left >>= 1; right >>= 1; } return op(sml, smr); } pll all_prod() { return d[1]; } // apply f (a pair) to [l, r) void apply(int l, int r, const pll &f) { // if r is omitted (single point), Python used different branch; here we implement both forms if (r <= l) return; int left = l + size, right = r + size; for (int i = _log; i >= 1; --i) { if (((left >> i) << i) != left) _push(left >> i); if (((right >> i) << i) != right) _push((right - 1) >> i); } int l2 = left, r2 = right; while (left < right) { if (left & 1) { _all_apply(left, f); ++left; } if (right & 1) { --right; _all_apply(right, f); } left >>= 1; right >>= 1; } left = l2; right = r2; for (int i = 1; i <= _log; ++i) { if (((left >> i) << i) != left) _update(left >> i); if (((right >> i) << i) != right) _update((right - 1) >> i); } } }; // Lazy segment tree specialized for long long with range-add of ll struct LazySegLL { int n; int _log; int size; vector<ll> d; vector<ll> lz; ll e = 0; ll id = 0; static int ceil_pow2(int n) { int x = 0; while ((1 << x) < n) ++x; return x; } LazySegLL(int n_, ll e_ = 0, ll id_ = 0) { n = n_; e = e_; id = id_; if (n == 0) { _log = 0; size = 1; } else { _log = ceil_pow2(n); size = 1 << _log; } d.assign(2*size, e); lz.assign(size, id); } LazySegLL(const vector<ll> &v, ll e_ = 0, ll id_ = 0) { n = (int)v.size(); e = e_; id = id_; _log = ceil_pow2(n); size = 1 << _log; d.assign(2*size, e); lz.assign(size, id); for (int i = 0; i < n; ++i) d[size + i] = v[i]; for (int i = size - 1; i >= 1; --i) d[i] = d[2*i] + d[2*i+1]; } void _update(int k) { d[k] = d[2*k] + d[2*k+1]; } void _all_apply(int k, ll f) { d[k] += f; if (k < size) lz[k] += f; } void _push(int k) { _all_apply(2*k, lz[k]); _all_apply(2*k+1, lz[k]); lz[k] = id; } void set(int p, ll x) { int pp = p + size; for (int i = _log; i >= 1; --i) _push(pp >> i); d[pp] = x; for (int i = 1; i <= _log; ++i) _update(pp >> i); } ll get(int p) { int pp = p + size; for (int i = _log; i >= 1; --i) _push(pp >> i); return d[pp]; } ll prod(int l, int r) { if (l == r) return e; int left = l + size, right = r + size; for (int i = _log; i >= 1; --i) { if (((left >> i) << i) != left) _push(left >> i); if (((right >> i) << i) != right) _push((right - 1) >> i); } ll sml = e, smr = e; while (left < right) { if (left & 1) { sml = sml + d[left]; ++left; } if (right & 1) { --right; smr = d[right] + smr; } left >>= 1; right >>= 1; } return sml + smr; } void apply(int l, int r, ll f) { if (r <= l) return; int left = l + size, right = r + size; for (int i = _log; i >= 1; --i) { if (((left >> i) << i) != left) _push(left >> i); if (((right >> i) << i) != right) _push((right - 1) >> i); } int l2 = left, r2 = right; while (left < right) { if (left & 1) { _all_apply(left, f); ++left; } if (right & 1) { --right; _all_apply(right, f); } left >>= 1; right >>= 1; } left = l2; right = r2; for (int i = 1; i <= _log; ++i) { if (((left >> i) << i) != left) _update(left >> i); if (((right >> i) << i) != right) _update((right - 1) >> i); } } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); #if 0 // If you need to debug with the Python sample, you can enable custom inputs here. #endif int N, M; if (!(cin >> N >> M)) return 0; // iwai: vector of tuples (index, a, l, r) struct Iwai { int idx; ll a; int l; int r; }; vector<Iwai> iwai; iwai.reserve(N); for (int i = 0; i < N; ++i) { ll a; int l, r; cin >> a >> l >> r; --l; iwai.push_back({i, a, l, r}); } // Build T: pair segtree of length M, init (0,0) LazySegPair T(vector<pll>(M, {0,0}), {0,0}, {0,0}); // Build TT: ll segtree of length M, init 0 LazySegLL TT(vector<ll>(M, 0LL), 0LL, 0LL); for (auto &it : iwai) { ll a = it.a; int l = it.l, r = it.r; // T.apply(l, r, (a,1)) T.apply(l, r, pll{a, 1}); } for (auto &it : iwai) { int i = it.idx; ll a = it.a; // TT.set(i, a) TT.set(i, a); } long long ans = 0; for (auto &it : iwai) { ll a = it.a; int l = it.l, r = it.r; ans += a * ll(r - l) - TT.prod(l, r); } int Q; cin >> Q; for (int qi = 0; qi < Q; ++qi) { int x, y, u, v; cin >> x >> y >> u >> v; --x; --y; --u; int now = iwai[x].idx; ll a = iwai[x].a; int l = iwai[x].l, r = iwai[x].r; iwai[x] = { y, a, u, v }; // まわりからの影響 T.apply(l, r, pll{-a, -1}); pll value_num = T.get(now); ll value = value_num.first; ll num = value_num.second; ans += a * num; // 元いた場所の自分の影響 ll sval = TT.prod(l, r); ans -= a * ll(r - l) - sval; TT.apply(now, now+1, -a); // 新転地の自分の影響 TT.apply(y, y+1, a); ans += a * ll(v - u) - TT.prod(u, v); // 新転地の周りの影響 pll p = T.prod(y, y+1); ll around_value = p.first; ll around_num = p.second; ans += -a * around_num; T.apply(u, v, pll{a, 1}); cout << ans << '\n'; // Debug prints (commented out to match original behavior) // cerr << "T :"; // for (int i = 0; i < M; ++i) { auto pr = T.get(i); cerr << "(" << pr.first << "," << pr.second << ") "; } // cerr << "\nTT :"; // for (int i = 0; i < M; ++i) cerr << TT.get(i) << " "; // cerr << "\n"; } return 0; }