結果
問題 |
No.879 Range Mod 2 Query
|
ユーザー |
![]() |
提出日時 | 2019-08-04 18:44:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 211 ms / 3,000 ms |
コード長 | 3,486 bytes |
コンパイル時間 | 2,077 ms |
コンパイル使用メモリ | 208,904 KB |
最終ジャッジ日時 | 2025-01-07 10:41:20 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} template <typename T,typename E> struct SegmentTree{ using F = function<T(T,T)>; using G = function<T(T,E)>; using H = function<E(E,E)>; int n,height; F f; G g; H h; T ti; E ei; vector<T> dat; vector<E> laz; SegmentTree(F f,G g,H h,T ti,E ei): f(f),g(g),h(h),ti(ti),ei(ei){} void init(int n_){ n=1;height=0; while(n<n_) n<<=1,height++; dat.assign(2*n,ti); laz.assign(2*n,ei); } void build(const vector<T> &v){ int n_=v.size(); init(n_); for(int i=0;i<n_;i++) dat[n+i]=v[i]; for(int i=n-1;i;i--) dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]); } inline T reflect(int k){ return laz[k]==ei?dat[k]:g(dat[k],laz[k]); } inline void eval(int k){ if(laz[k]==ei) return; laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]); laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]); dat[k]=reflect(k); laz[k]=ei; } inline void thrust(int k){ for(int i=height;i;i--) eval(k>>i); } inline void recalc(int k){ while(k>>=1) dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1)); } void update(int a,int b,E x){ thrust(a+=n); thrust(b+=n-1); for(int l=a,r=b+1;l<r;l>>=1,r>>=1){ if(l&1) laz[l]=h(laz[l],x),l++; if(r&1) --r,laz[r]=h(laz[r],x); } recalc(a); recalc(b); } void set_val(int a,T x){ thrust(a+=n); dat[a]=x;laz[a]=ei; recalc(a); } T query(int a,int b){ thrust(a+=n); thrust(b+=n-1); T vl=ti,vr=ti; for(int l=a,r=b+1;l<r;l>>=1,r>>=1) { if(l&1) vl=f(vl,reflect(l++)); if(r&1) vr=f(reflect(--r),vr); } return f(vl,vr); } }; struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; //INSERT ABOVE HERE signed main(){ using ll = long long; int n,q; cin>>n>>q; vector<ll> as(n); for(int i=0;i<n;i++) cin>>as[i]; struct T{ ll odd,evn,sum; T():odd(0),evn(0),sum(0){} T(ll odd,ll evn,ll sum):odd(odd),evn(evn),sum(sum){} }; struct E{ ll pre,flg,add; E():pre(0),flg(0),add(0){} E(ll pre,ll flg,ll add):pre(pre),flg(flg),add(add){} bool operator==(const E &a) const{ return pre==a.pre&&flg==a.flg&&add==a.add; } }; auto f= [&](T a,T b){ return T(a.odd+b.odd,a.evn+b.evn,a.sum+b.sum); }; auto g= [&](T a,E b){ T res=a; if(b.flg){ if(b.pre&1) swap(res.odd,res.evn); res.sum=res.odd; } res.sum+=(res.odd+res.evn)*b.add; if(b.add&1) swap(res.odd,res.evn); return res; }; auto h= [&](E a,E b){ E res=a; if(b.flg){ res.pre=a.pre+a.add+b.pre; res.flg=1; res.add=b.add; return res; } res.add+=b.add; return res; }; T ti(0,0,0); E ei(0,0,0); SegmentTree<T, E> seg(f,g,h,ti,ei); vector<T> vt; for(int i=0;i<n;i++) vt.emplace_back(as[i]&1,~as[i]&1,as[i]); seg.build(vt); for(int i=0;i<q;i++){ int t; cin>>t; if(t==1){ int l,r; cin>>l>>r; l--; seg.update(l,r,E(0,1,0)); } if(t==2){ int l,r,x; cin>>l>>r>>x; l--; seg.update(l,r,E(0,0,x)); } if(t==3){ int l,r; cin>>l>>r; l--; cout<<seg.query(l,r).sum<<"\n"; } } cout<<flush; return 0; }