結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:28:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,363 ms / 2,500 ms |
コード長 | 7,503 bytes |
コンパイル時間 | 2,626 ms |
コンパイル使用メモリ | 212,176 KB |
実行使用メモリ | 25,216 KB |
最終ジャッジ日時 | 2025-09-06 14:29:22 |
合計ジャッジ時間 | 54,528 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; // C++に書き換えただけで通る?? template <typename T, typename M, T OP(T, T), T MAPPING(T, M, int), T COMPOSITION(T, T)> class LazySegmentTree { private: int _treeSize; int _dataSize; int _originalDataSize; vector<T> _data; vector<optional<T>> _lazy; T _identity; public: LazySegmentTree(int n, T identity) { _originalDataSize = n; _identity = identity; int size = 1; while (n > size) { size <<= 1; } _dataSize = size; _treeSize = 2 * size - 1; _data.resize(_treeSize, _identity); _lazy.resize(_treeSize, nullopt); } void Build(vector<T>& array) { if (_originalDataSize != (int)array.size()) { throw exception(); } for (int i = 0; i < (int)array.size(); i++) { _data[i + _dataSize - 1] = array[i]; } for (int i = _dataSize - 2; i >= 0; i--) { _data[i] = OP(_data[(i << 1) + 1], _data[(i << 1) + 2]); } } int TreeSize() { return _treeSize; } int OriginalDataSize() { return _originalDataSize; } void Apply(int left, int right, M m) { ApplyRec(left, right, m, 0, 0, _dataSize); } T Query(int left, int right) { return QueryRec(left, right, 0, 0, _dataSize); } T GetByIndex(int index) { return AccessRec(index, 0, 0, _dataSize); } private: void Evaluate(int index, int l, int r) { if (!_lazy[index].has_value()) { return; } if (index < _dataSize - 1) { _lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]); _lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]); } _data[index] = MAPPING(_data[index], _lazy[index].value(), r - l); _lazy[index] = nullopt; } optional<M> GuardComposition(optional<M> a, optional<M> b) { if (!a.has_value()) { return b; } else { return COMPOSITION(a.value(), b.value()); } } void ApplyRec(int left, int right, M m, int index, int l, int r) { Evaluate(index, l, r); if (left <= l && r <= right) { _lazy[index] = GuardComposition(_lazy[index], m); Evaluate(index, l, r); } else if (left < r && l < right) { ApplyRec(left, right, m, (index << 1) + 1, l, (l + r) / 2); ApplyRec(left, right, m, (index << 1) + 2, (l + r) / 2, r); _data[index] = OP(_data[(index << 1) + 1], _data[(index << 1) + 2]); } } T QueryRec(int left, int right, int index, int l, int r) { Evaluate(index, l, r); if (left >= r || right <= l) { return _identity; } if (left <= l && r <= right) { return _data[index]; } return OP(QueryRec(left, right, (index << 1) + 1, l, (l + r) / 2), QueryRec(left, right, (index << 1) + 2, (l + r) / 2, r)); } T AccessRec(int target, int index, int l, int r) { Evaluate(index, l, r); if (index >= _dataSize - 1) { return _data[index]; } int mid = (l + r) / 2; if (target < mid) { return AccessRec(target, (index << 1) + 1, l, mid); } else { return AccessRec(target, (index << 1) + 2, mid, r); } } }; template<typename T, T OP(T, T), T APPLY(T, T)> class SegmentTree { private: int _treeSize; int _dataSize; int _originalDataSize; vector<T> _data; T _identity; public: SegmentTree(int n, T identity) { _originalDataSize = n; _identity = identity; int size = 1; while (n > size) { size <<= 1; } _dataSize = size; _treeSize = 2 * size - 1; _data.resize(_treeSize, _identity); } int OriginalDataSize() { return _originalDataSize; } int TreeSize() { return _treeSize; } T Identity() { return _identity; } void Build(vector<T>& array) { if (_originalDataSize != (int)array.size()) { throw exception(); } for (int i = 0; i < (int)array.size(); i++) { _data[i + _dataSize - 1] = array[i]; } for (int i = _dataSize - 2; i >= 0; i--) { _data[i] = OP(_data[(i << 1) + 1], _data[(i << 1) + 2]); } } void Apply(int index, T value) { index += _dataSize - 1; _data[index] = APPLY(_data[index], value); while (index > 0) { index = (index - 1) >> 1; _data[index] = OP(_data[(index << 1) + 1], _data[(index << 1) + 2]); } } T Query(int left, int right) { return QueryRec(left, right, 0, 0, _dataSize); } const T& operator[](size_t index) const { return _data[_dataSize - 1 + index]; } T& operator[](size_t index) { return _data[_dataSize - 1 + index]; } private: T QueryRec(int left, int right, int index, int l, int r) { if (left >= r || right <= l) { return _identity; } if (left <= l && r <= right) { return _data[index]; } return OP(QueryRec(left, right, (index << 1) + 1, l, (l + r) / 2), QueryRec(left, right, (index << 1) + 2, (l + r) / 2, r)); } }; ll update(ll x, ll a) { return a; } ll add(ll x, ll y) { return x + y; } ll mapping(ll x, ll a, int len) { return x + a * len; } int main(int argc, char** argv) { cin.tie(nullptr); ios::sync_with_stdio(false); int N, M; cin >> N >> M; vector<ll> A(N); vector<int> L(N); vector<int> R(N); for (int i = 0; i < N; i++) { cin >> A[i] >> L[i] >> R[i]; L[i]--; R[i]--; } vector<int> home(N); for (int i = 0; i < N; i++) home[i] = i; vector<ll> B(M); for (int i = 0; i < N; i++) B[i] = A[i]; SegmentTree<ll, add, update> seg(M, 0LL); LazySegmentTree<ll, ll, add, mapping, add> nseg(M, 0LL); seg.Build(B); for (int i = 0; i < N; i++) { nseg.Apply(L[i], R[i] + 1, 1); } long sum = 0; for (int i = 0; i < N; i++) { sum += A[i] * (R[i] - L[i] + 1) - seg.Query(L[i], R[i] + 1); } int Q; cin >> Q; for (int i = 0; i < Q; i++) { int x, y, u, v; cin >> x >> y >> u >> v; x--; y--; u--; v--; // 差分更新を、がんばる int from = home[x]; sum -= A[x] * (R[x] - L[x] + 1); sum += seg.Query(L[x], R[x] + 1); sum += A[x] * nseg.GetByIndex(from); if (L[x] <= from && from <= R[x]) sum -= A[x]; seg.Apply(y, A[x]); seg.Apply(from, 0); nseg.Apply(L[x], R[x] + 1, -1); home[x] = y; L[x] = u; R[x] = v; nseg.Apply(u, v + 1, 1); sum += A[x] * (v - u + 1); sum -= seg.Query(u, v + 1); sum -= A[x] * nseg.GetByIndex(y); if (u <= y && y <= v) sum += A[x]; cout << sum << endl; } }