結果
問題 | No.879 Range Mod 2 Query |
ユーザー |
|
提出日時 | 2023-05-12 03:59:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 131 ms / 3,000 ms |
コード長 | 1,256 bytes |
コンパイル時間 | 3,662 ms |
コンパイル使用メモリ | 233,960 KB |
実行使用メモリ | 14,720 KB |
最終ジャッジ日時 | 2024-11-27 22:47:26 |
合計ジャッジ時間 | 6,197 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; using S = array<ll, 3>; using F = array<ll, 3>; S e(){return S({0, 0, 0});} S op(S l, S r){ for(int i = 0; i < 3; i++) l[i] += r[i]; return l; } S mapping(F f, S x){ S res{}; if(f[1] & 1) swap(x[0], x[1]); x[2] += (x[0] + x[1]) * f[1]; if(f[0] == 1) x[2] = x[1]; if(f[2] & 1) swap(x[0], x[1]); x[2] += (x[0] + x[1]) * f[2]; return x; } F composition(F f, F g){ if(f[0] == 0) return S({g[0], g[1], g[2] + f[1] + f[2]}); return S({1, g[1] + g[2] + f[1], f[2]}); } F id(){return F({0, 0, 0});} int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, Q; cin >> N >> Q; vector<S> tmp(N); for(int i = 0; i < N; i++){ int v; cin >> v; tmp[i] = S({1 - v % 2, v % 2, v}); } atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(tmp); while(Q--){ int cmd, l, r, x; cin >> cmd >> l >> r; l--; if(cmd == 1){ seg.apply(l, r, F({1, 0, 0})); }else if(cmd == 2){ cin >> x; seg.apply(l, r, F({0, 0, x})); }else{ cout << seg.prod(l, r)[2] << '\n'; } } }