結果
問題 | No.749 クエリ全部盛り |
ユーザー |
![]() |
提出日時 | 2021-02-16 00:59:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 337 ms / 3,000 ms |
コード長 | 1,619 bytes |
コンパイル時間 | 2,485 ms |
コンパイル使用メモリ | 211,084 KB |
最終ジャッジ日時 | 2025-01-18 21:21:01 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; __attribute__((constructor)) void fast_io() { ios::sync_with_stdio(false); cin.tie(nullptr); } #include <atcoder/modint> #include <atcoder/lazysegtree> using namespace atcoder; using mint = modint1000000007; using S = tuple<mint, mint, mint>; S op(S a, S b) { auto [p, q, r] = a; auto [s, t, u] = b; return {p + s, q + t, r + u}; } S e() { return {0, 0, 0}; } using F = tuple<mint, mint, mint>; S mapping(F f, S x) { auto [p, q, r] = f; auto [s, t, u] = x; return {p * s + q * t + r * u, t, u}; } F composition(F f, F g) { auto [p, q, r] = f; auto [s, t, u] = g; return {p * s, p * t + q, p * u + r}; } F id() { return {1, 0, 0}; } int main() { int n, q; cin >> n >> q; vector<mint> f(n); vector<S> a(n); for (int i = 0; i < n; ++i) { if (i == 0) f[0] = 0; else if (i == 1) f[1] = 1; else f[i] = f[i - 1] + f[i - 2]; auto& [p, q, r] = a[i]; q = f[i]; r = 1; } lazy_segtree<S, op, e, F, mapping, composition, id> seg(a); for (int i = 0; i < q; ++i) { int q, l, r, k; cin >> q >> l >> r >> k; if (q == 0) { mint ans = k * get<0>(seg.prod(l, r + 1)); cout << ans.val() << '\n'; } if (q == 1) { seg.apply(l, r + 1, {0, 0, k}); } if (q == 2) { seg.apply(l, r + 1, {1, 0, k}); } if (q == 3) { seg.apply(l, r + 1, {k, 0, 0}); } if (q == 4) { seg.apply(l, r + 1, {1, k, 0}); } } }