結果
| 問題 |
No.3265 地元に帰れば天才扱い！
|
| ユーザー |
 kidodesu
|
| 提出日時 | 2025-09-06 14:28:51 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 925 ms / 2,500 ms |
| コード長 | 11,389 bytes |
| コンパイル時間 | 2,583 ms |
| コンパイル使用メモリ | 208,096 KB |
| 実行使用メモリ | 26,704 KB |
| 最終ジャッジ日時 | 2025-09-06 14:29:49 |
| 合計ジャッジ時間 | 24,992 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 21 |
ソースコード
/*
gptによりpythonからC++に変換
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 = map(int, input().split()) # n < m <= 2e5
A = [0] * m
LR = [[-1, -1] for _ in range(m)]
lst = [0] * (m+1)
ans = 0
for i in range(n):
a, l, r = map(int, input().split()) #0 <= a <= 1e8, 1 <= l <= r <= m
A[i] = a
LR[i] = [l-1, r]
lst[l-1] += 1
lst[r] -= 1
ans += a * (r - l + 1)
q = int(input()) # q <= 2e5
for i in range(1, m):
lst[i] += lst[i-1]
for i in range(m): ans -= A[i] * lst[i]
I = [i for i in range(n)]
st0 = LazySegTree(lambda a, b: a+b, 0, lambda a, b: a+b, lambda a, b: a+b, 0, A)
st1 = LazySegTree(lambda a, b: a+b, 0, lambda a, b: a+b, lambda a, b: a+b, 0, lst[:-1])
for _ in range(q):
x, y, u, v = map(int, input().split()) # x <= n, y <= m, 1 <= u <= v <= m
x -= 1; y -= 1; u -= 1
x0 = I[x]
I[x] = y
x = x0
a = st0.get(x)
ans += a * st1.get(x) - a * st1.get(y)
st0.set(x, 0)
st0.set(y, a)
l, r = LR[x]
st1.apply(l, r, -1)
ans -= a * (r - l) - a * (v - u)
ans += st0.prod(l, r) - st0.prod(u, v)
st1.apply(u, v, 1)
LR[y] = [u, v]
print(ans)
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct LazySegTree {
int n;
int size;
int logv;
vector<ll> d;
vector<ll> lz;
vector<int> seglen;
LazySegTree() : n(0), size(0), logv(0) {}
LazySegTree(const vector<ll>& v) { build(v); }
void build(const vector<ll>& v) {
n = (int)v.size();
logv = 0;
while ((1 << logv) < n) ++logv;
size = 1 << logv;
d.assign(2 * size, 0);
lz.assign(size, 0);
seglen.assign(2 * size, 0);
for (int i = 0; i < size; ++i) seglen[size + i] = (i < n ? 1 : 0);
for (int i = size - 1; i >= 1; --i) seglen[i] = seglen[2*i] + seglen[2*i+1];
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 all_apply(int k, ll f) {
if (f == 0) return;
d[k] += f * seglen[k];
if (k < size) lz[k] += f;
}
void push(int k) {
if (lz[k] != 0) {
all_apply(2*k, lz[k]);
all_apply(2*k+1, lz[k]);
lz[k] = 0;
}
}
void pull(int k) { d[k] = d[2*k] + d[2*k+1]; }
void set_val(int p, ll x) {
p += size;
for (int i = logv; i >= 1; --i) push(p >> i);
d[p] = x;
for (int i = 1; i <= logv; ++i) pull(p >> i);
}
ll get(int p) {
p += size;
for (int i = logv; i >= 1; --i) push(p >> i);
return d[p];
}
ll prod(int l, int r) {
if (l == r) return 0;
l += size; r += size;
for (int i = logv; i >= 1; --i) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
ll sml = 0, smr = 0;
while (l < r) {
if (l & 1) sml += d[l++];
if (r & 1) smr = d[--r] + smr;
l >>= 1; r >>= 1;
}
return sml + smr;
}
void apply(int l, int r, ll f) {
if (l == r) return;
int l0 = l + size, r0 = r + size;
for (int i = logv; i >= 1; --i) {
if (((l0 >> i) << i) != l0) push(l0 >> i);
if (((r0 >> i) << i) != r0) push((r0 - 1) >> i);
}
int L = l0, R = r0;
while (L < R) {
if (L & 1) { all_apply(L++, f); }
if (R & 1) { all_apply(--R, f); }
L >>= 1; R >>= 1;
}
for (int i = 1; i <= logv; ++i) {
if (((l0 >> i) << i) != l0) pull(l0 >> i);
if (((r0 >> i) << i) != r0) pull((r0 - 1) >> i);
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<ll> A(m, 0);
vector<pair<int,int>> LR(m, {-1,-1});
vector<ll> lst(m+1, 0);
ll ans = 0;
for (int i = 0; i < n; ++i) {
ll a; int l, r;
cin >> a >> l >> r;
A[i] = a;
LR[i] = {l-1, r};
lst[l-1] += 1;
lst[r] -= 1;
ans += a * (r - l + 1);
}
int q;
cin >> q;
for (int i = 1; i < m; ++i) lst[i] += lst[i-1];
for (int i = 0; i < m; ++i) ans -= A[i] * lst[i];
vector<int> I(n);
for (int i = 0; i < n; ++i) I[i] = i;
LazySegTree st0(vector<ll>(A.begin(), A.end()));
vector<ll> lstm(m);
for (int i = 0; i < m; ++i) lstm[i] = lst[i];
LazySegTree st1(lstm);
for (int qi = 0; qi < q; ++qi) {
int x, y, u, v;
cin >> x >> y >> u >> v;
--x; --y; --u;
int x0 = I[x];
I[x] = y;
x = x0;
ll a = st0.get(x);
ans += a * st1.get(x) - a * st1.get(y);
st0.set_val(x, 0);
st0.set_val(y, a);
int l = LR[x].first;
int r = LR[x].second;
st1.apply(l, r, -1);
ans -= a * ( (ll)(r - l) ) - a * ( (ll)(v - u) );
ans += st0.prod(l, r) - st0.prod(u, v);
st1.apply(u, v, 1);
LR[y] = {u, v};
cout << ans << '\n';
}
return 0;
}