結果
問題 | No.880 Yet Another Segment Tree Problem |
ユーザー |
![]() |
提出日時 | 2019-08-06 19:50:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,089 bytes |
コンパイル時間 | 2,212 ms |
コンパイル使用メモリ | 211,112 KB |
最終ジャッジ日時 | 2025-01-07 10:50:57 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 32 TLE * 5 |
ソースコード
#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); } template<typename Uku, typename Check, typename Func, typename U> void update(int a,int b,Uku uku,Check check,Func func,U x,int l,int r,int k){ if(l+1<r) eval(k); if(r<=a||b<=l||uku(reflect(k))) return; if(a<=l&&r<=b&&check(reflect(k))){ tie(dat[k],laz[k])=func(reflect(k),x); if(l+1<r) eval(k); return; } int m=(l+r)>>1; update(a,b,uku,check,func,x,l,m,(k<<1)|0); update(a,b,uku,check,func,x,m,r,(k<<1)|1); dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1)); } template<typename Uku, typename Check, typename Func, typename U> void update(int a,int b,Uku uku,Check check,Func func,U x){ update(a,b,uku,check,func,x,0,n,1); } }; struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; //INSERT ABOVE HERE signed main(){ int n,q; cin>>n>>q; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i]; using ll = long long; struct T{ ll ma,mi,len,sum; T(ll ma,ll mi,ll len,ll sum):ma(ma),mi(mi),len(len),sum(sum){} }; using E = ll; auto f=[&](T a,T b){ return T(max(a.ma,b.ma),min(a.mi,b.mi),a.len+b.len,a.sum+b.sum); }; auto g=[&](T a,E b){ return T(b,b,a.len,a.len*b); }; auto h=[&](E a,E b){ (void)a; assert(~b); return b; }; const ll INF = 1e9+1; T ti(-INF,+INF,0,0); E ei(-1); SegmentTree<T, E> seg(f,g,h,ti,ei); vector<T> vt; for(int i=0;i<n;i++) vt.emplace_back(as[i],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,x; cin>>l>>r>>x; l--; seg.update(l,r,x); } if(t==2){ using U = ll; auto uku=[&](T a){return a.ma==1;}; auto check=[&](T a){return a.ma==a.mi;}; auto func=[&](T a,U x){ assert(check(a)); return make_pair(a,E(__gcd(a.ma,x))); }; int l,r; cin>>l>>r; l--; U x; cin>>x; seg.update(l,r,uku,check,func,x); } if(t==3){ int l,r; cin>>l>>r; l--; cout<<seg.query(l,r).ma<<"\n"; } if(t==4){ int l,r; cin>>l>>r; l--; cout<<seg.query(l,r).sum<<"\n"; } } cout<<flush; return 0; }