結果
問題 | No.880 Yet Another Segment Tree Problem |
ユーザー | beet |
提出日時 | 2019-09-03 11:25:20 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 705 ms / 5,000 ms |
コード長 | 4,772 bytes |
コンパイル時間 | 2,611 ms |
コンパイル使用メモリ | 216,572 KB |
実行使用メモリ | 20,976 KB |
最終ジャッジ日時 | 2023-10-24 02:36:08 |
合計ジャッジ時間 | 12,952 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,372 KB |
testcase_01 | AC | 3 ms
4,372 KB |
testcase_02 | AC | 3 ms
4,372 KB |
testcase_03 | AC | 3 ms
4,372 KB |
testcase_04 | AC | 3 ms
4,372 KB |
testcase_05 | AC | 3 ms
4,372 KB |
testcase_06 | AC | 3 ms
4,372 KB |
testcase_07 | AC | 3 ms
4,372 KB |
testcase_08 | AC | 3 ms
4,372 KB |
testcase_09 | AC | 4 ms
4,372 KB |
testcase_10 | AC | 3 ms
4,372 KB |
testcase_11 | AC | 474 ms
20,800 KB |
testcase_12 | AC | 463 ms
20,840 KB |
testcase_13 | AC | 328 ms
18,724 KB |
testcase_14 | AC | 452 ms
20,936 KB |
testcase_15 | AC | 491 ms
20,936 KB |
testcase_16 | AC | 513 ms
20,952 KB |
testcase_17 | AC | 705 ms
20,976 KB |
testcase_18 | AC | 687 ms
20,976 KB |
testcase_19 | AC | 174 ms
20,936 KB |
testcase_20 | AC | 171 ms
20,976 KB |
testcase_21 | AC | 170 ms
20,912 KB |
testcase_22 | AC | 169 ms
20,952 KB |
testcase_23 | AC | 170 ms
20,920 KB |
testcase_24 | AC | 153 ms
20,936 KB |
testcase_25 | AC | 161 ms
20,976 KB |
testcase_26 | AC | 154 ms
20,912 KB |
testcase_27 | AC | 161 ms
20,952 KB |
testcase_28 | AC | 162 ms
20,920 KB |
testcase_29 | AC | 440 ms
20,936 KB |
testcase_30 | AC | 473 ms
20,936 KB |
testcase_31 | AC | 511 ms
20,952 KB |
testcase_32 | AC | 111 ms
20,976 KB |
testcase_33 | AC | 133 ms
20,936 KB |
testcase_34 | AC | 139 ms
20,944 KB |
testcase_35 | AC | 132 ms
20,936 KB |
testcase_36 | AC | 131 ms
20,960 KB |
testcase_37 | AC | 135 ms
20,952 KB |
ソースコード
#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,typename F,typename G,typename H> struct SegmentTree{ 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,typename F2> void update(int a,int b,Uku uku,Check check,Func func,U x,F2 f2,int l,int r,int k){ if(l+1<r) eval(k); if(r<=a||b<=l||uku(reflect(k),x)) 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,f2,l,m,(k<<1)|0); update(a,b,uku,check,func,x,f2,m,r,(k<<1)|1); if(a<=l&&r<=b) dat[k]=f2(dat[k],reflect((k<<1)|0),reflect((k<<1)|1),x); else dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1)); } template<typename Uku, typename Check, typename Func, typename U,typename F2> void update(int a,int b,Uku uku,Check check,Func func,U x,F2 f2){ update(a,b,uku,check,func,x,f2,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,lcm,len,sum; T(ll ma,ll mi,ll lcm,ll len,ll sum):ma(ma),mi(mi),lcm(lcm),len(len),sum(sum){} }; using E = ll; const ll INF = 1e9+1; auto mlcm=[&](ll x,ll y){ if(x>=INF||y>=INF) return INF; ll z=x/__gcd(x,y)*y; return min(z,INF); }; auto f=[&](T a,T b){ return T(max(a.ma,b.ma), min(a.mi,b.mi), mlcm(a.lcm,b.lcm), a.len+b.len, a.sum+b.sum); }; auto g=[&](T a,E b){ return T(b,b,b,a.len,a.len*b); }; auto h=[&](E a,E b){ (void)a; return b; }; T ti(-INF,+INF,1,0,0); E ei(-1); SegmentTree<T, E, decltype(f), decltype(g), decltype(h)> seg(f,g,h,ti,ei); vector<T> vt; for(int i=0;i<n;i++) vt.emplace_back(as[i],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,U x){return a.lcm<=x&&x%a.lcm==0;}; 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))); }; auto f2=[&](T t,T a,T b,U x){ return T(max(a.ma,b.ma), min(a.mi,b.mi), t.lcm==INF?mlcm(a.lcm,b.lcm):__gcd(t.lcm,x), a.len+b.len, a.sum+b.sum); }; int l,r; cin>>l>>r; l--; U x; cin>>x; seg.update(l,r,uku,check,func,x,f2); } 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; }