結果
| 問題 |
No.3265 地元に帰れば天才扱い！
|
| ユーザー |
 yuuDot
|
| 提出日時 | 2025-09-06 15:42:34 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,335 ms / 2,500 ms |
| コード長 | 6,944 bytes |
| コンパイル時間 | 4,454 ms |
| コンパイル使用メモリ | 210,088 KB |
| 実行使用メモリ | 28,300 KB |
| 最終ジャッジ日時 | 2025-09-06 15:43:12 |
| 合計ジャッジ時間 | 34,358 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 21 |
ソースコード
/*
from atcoder.lazysegtree import LazySegTree
from atcoder.segtree import SegTree
n, m = map(int, input().split())
rate = [0] * m
each_range = [(0, 0)] * m
pos = [0] * m
ID = 0
# (sum, length)
def op(x, y):
return (x[0] + y[0], x[1] + y[1])
def e():
return (0, 0)
def mapping(f, x):
if f == ID:
return x
return (f * x[1] + x[0], x[1])
def composition(f_new, f_old):
if f_new == ID:
return f_old
return f_new + f_old
lst = LazySegTree(op, e(), mapping, composition, ID, [(0, 1)] * m)
for i in range(n):
a, l, r = map(int, input().split())
rate[i] = a
pos[i] = i
each_range[i] = (l, r)
lst.apply(l - 1, r, 1)
# for i in range(m):
# print(lst.get(i), end=" ")
# exit()
st = SegTree(lambda x, y: x + y, 0, rate)
crr_ans = 0
for i in range(m):
if rate[i] == 0:
continue
l, r = each_range[i]
crr_ans += rate[i] * (r - l + 1) - st.prod(l - 1, r)
ans = []
q = int(input())
for _ in range(q):
x, y, u, v = map(int, input().split())
x -= 1
y -= 1
px = pos[x]
# 何人の範囲にかぶっていたか
l, r = each_range[px]
minus = lst.get(px)[0]
if l - 1 <= px < r:
minus -= 1
crr_ans += rate[px] * minus
lst.apply(l - 1, r, -1)
# 引っ越す前の本人の天才度
crr_ans -= rate[px] * (r - l + 1) - st.prod(l - 1, r)
# レート更新とか
rate[y] = rate[px]
rate[px] = 0
st.set(px, 0)
st.set(y, rate[y])
each_range[px] = (0, 0)
each_range[y] = (u, v)
# 何人の範囲にかぶっているか
crr_ans -= rate[y] * lst.get(y)[0]
lst.apply(u - 1, v, 1)
# 引っ越した後の天才度
crr_ans += rate[y] * (v - u + 1) - st.prod(u - 1, v)
pos[x] = y
ans.append(crr_ans)
print(*ans, sep="\n")
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
ll sum;
ll len;
Node(): sum(0), len(0) {}
Node(ll s, ll l): sum(s), len(l) {}
};
struct LazySegTree {
int n;
int size_;
vector<Node> seg;
vector<ll> lazy;
const ll ID = 0;
LazySegTree() { n = 0; size_ = 0; }
Node op(const Node &a, const Node &b) {
return Node(a.sum + b.sum, a.len + b.len);
}
Node e() { return Node(0, 0); }
Node mapping(ll f, const Node &x) {
if (f == ID) return x;
return Node(f * x.len + x.sum, x.len);
}
ll composition(ll f_new, ll f_old) {
if (f_new == ID) return f_old;
return f_new + f_old;
}
void build(const vector<Node> &v) {
n = (int)v.size();
size_ = 1;
while (size_ < n) size_ <<= 1;
seg.assign(2 * size_, e());
lazy.assign(2 * size_, ID);
for (int i = 0; i < n; ++i) seg[size_ + i] = v[i];
for (int i = size_ - 1; i >= 1; --i) seg[i] = op(seg[2*i], seg[2*i+1]);
}
void push(int k) {
if (lazy[k] != ID && k < size_) {
ll f = lazy[k];
int lc = 2*k, rc = 2*k+1;
seg[lc] = mapping(f, seg[lc]);
seg[rc] = mapping(f, seg[rc]);
lazy[lc] = composition(f, lazy[lc]);
lazy[rc] = composition(f, lazy[rc]);
lazy[k] = ID;
}
}
void range_apply(int a, int b, ll f) { range_apply(a, b, f, 1, 0, size_); }
void range_apply(int a, int b, ll f, int k, int l, int r) {
if (a >= r || b <= l) return;
if (a <= l && r <= b) {
seg[k] = mapping(f, seg[k]);
lazy[k] = composition(f, lazy[k]);
return;
}
push(k);
int mid = (l + r) >> 1;
range_apply(a, b, f, 2*k, l, mid);
range_apply(a, b, f, 2*k+1, mid, r);
seg[k] = op(seg[2*k], seg[2*k+1]);
}
Node prod(int a, int b) { return prod(a, b, 1, 0, size_); }
Node prod(int a, int b, int k, int l, int r) {
if (a >= r || b <= l) return e();
if (a <= l && r <= b) return seg[k];
push(k);
int mid = (l + r) >> 1;
return op(prod(a, b, 2*k, l, mid), prod(a, b, 2*k+1, mid, r));
}
Node get(int idx) { return prod(idx, idx+1); }
};
struct SegTree {
int n;
int size_;
vector<ll> seg;
ll e = 0;
SegTree() { n = 0; size_ = 0; }
void build(const vector<ll> &v) {
n = (int)v.size();
size_ = 1;
while (size_ < n) size_ <<= 1;
seg.assign(2 * size_, e);
for (int i = 0; i < n; ++i) seg[size_ + i] = v[i];
for (int i = size_ - 1; i >= 1; --i) seg[i] = seg[2*i] + seg[2*i+1];
}
void set(int idx, ll val) {
int k = size_ + idx;
seg[k] = val;
while (k > 1) {
k >>= 1;
seg[k] = seg[2*k] + seg[2*k+1];
}
}
ll prod(int l, int r) { // [l, r)
if (l >= r) return 0;
l += size_; r += size_;
ll resl = e, resr = e;
while (l < r) {
if (l & 1) resl = resl + seg[l++];
if (r & 1) resr = seg[--r] + resr;
l >>= 1; r >>= 1;
}
return resl + resr;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<ll> rate(m, 0);
vector<pair<int,int>> each_range(m, {0,0});
vector<int> pos(n, 0);
const ll ID = 0;
vector<Node> init(m);
for (int i = 0; i < m; ++i) init[i] = Node(0, 1);
LazySegTree lst;
lst.build(init);
for (int i = 0; i < n; ++i) {
int a, l, r;
cin >> a >> l >> r;
rate[i] = a;
pos[i] = i;
each_range[i] = {l, r};
lst.range_apply(l - 1, r, 1);
}
SegTree st;
st.build(rate);
ll crr_ans = 0;
for (int i = 0; i < m; ++i) {
if (rate[i] == 0) continue;
int l = each_range[i].first;
int r = each_range[i].second;
ll len = (ll)(r - l + 1);
ll s = st.prod(l - 1, r);
crr_ans += rate[i] * len - s;
}
int q;
cin >> q;
vector<ll> answers;
answers.reserve(q);
for (int qi = 0; qi < q; ++qi) {
int x, y, u, v;
cin >> x >> y >> u >> v;
--x; --y;
int px = pos[x];
int l = each_range[px].first;
int r = each_range[px].second;
ll minus = lst.get(px).sum;
if (l - 1 <= px && px < r) minus -= 1;
crr_ans += rate[px] * minus;
lst.range_apply(l - 1, r, -1);
crr_ans -= rate[px] * (ll)(r - l + 1) - st.prod(l - 1, r);
rate[y] = rate[px];
rate[px] = 0;
st.set(px, 0);
st.set(y, rate[y]);
each_range[px] = {0, 0};
each_range[y] = {u, v};
crr_ans -= rate[y] * lst.get(y).sum;
lst.range_apply(u - 1, v, 1);
crr_ans += rate[y] * (ll)(v - u + 1) - st.prod(u - 1, v);
pos[x] = y;
answers.push_back(crr_ans);
}
for (size_t i = 0; i < answers.size(); ++i) {
cout << answers[i] << '\n';
}
return 0;
}