結果
問題 | No.776 A Simple RMQ Problem |
ユーザー |
![]() |
提出日時 | 2018-12-25 15:02:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 168 ms / 3,000 ms |
コード長 | 2,853 bytes |
コンパイル時間 | 2,364 ms |
コンパイル使用メモリ | 206,936 KB |
最終ジャッジ日時 | 2025-01-06 20:03:03 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#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)>; Int n; F f; G g; T ti; vector<T> dat; SegmentTree(){}; SegmentTree(F f,G g,T ti):f(f),g(g),ti(ti){} void init(Int n_){ n=1; while(n<n_) n<<=1; dat.assign(n<<1,ti); } 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]); } void update(Int k,E a){ k+=n; dat[k]=g(dat[k],a); while(k>>=1) dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]); } void set_val(Int k,T x){ dat[k+=n]=x; while(k>>=1) dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]); } T query(Int a,Int b){ T vl=ti,vr=ti; for(Int l=a+n,r=b+n;l<r;l>>=1,r>>=1) { if(l&1) vl=f(vl,dat[l++]); if(r&1) vr=f(dat[--r],vr); } return f(vl,vr); } }; struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; //INSERT ABOVE HERE signed main(){ Int n,q; cin>>n>>q; struct T{ Int va,vi,vl,vr; T(){} T(Int va,Int vi,Int vl,Int vr):va(va),vi(vi),vl(vl),vr(vr){} bool operator==(const T&a)const{ return va==a.va&&vi==a.vi&&vl==a.vl&&vr==a.vr; } }; const Int INF = 1e15; T ti(-INF,-INF,-INF,-INF); auto f=[&](T a,T b){ if(a==ti) return b; if(b==ti) return a; Int cva=a.va+b.va,cvi=max(a.vi,b.vi),cvl=a.vl,cvr=b.vr; chmax(cvi,a.vr+b.vl); chmax(cvl,a.va+b.vl); chmax(cvr,a.vr+b.va); return T(cva,cvi,cvl,cvr); }; auto g=[&](T a,Int b){a.va++;return T(b,b,b,b);}; SegmentTree<T, Int> seg(f,g,ti); seg.build(vector<T>(n,ti)); vector<Int> a(n); for(Int i=0;i<n;i++) cin>>a[i]; for(Int i=0;i<n;i++) seg.update(i,a[i]); for(Int i=0;i<q;i++){ string s; cin>>s; if(s=="set"s){ Int k,x; cin>>k>>x; k--; seg.update(k,x); } if(s=="max"s){ Int l1,l2,r1,r2; cin>>l1>>l2>>r1>>r2; l1--;r1--; chmin(l2,r2); chmax(r1,l1); if(l2<=r1){ auto x=seg.query(l1,l2); auto y=seg.query(r1,r2); auto z=seg.query(l2,r1); Int ans=x.vr+(l2==r1?0:z.va)+y.vl; cout<<ans<<"\n"; }else{ auto x=seg.query(l1,r1); auto y=seg.query(l2,r2); auto z=seg.query(r1,l2); Int ans=x.vr+z.va+y.vl; chmax(ans,z.vi); chmax(ans,z.vr+y.vl); chmax(ans,x.vr+z.vl); cout<<ans<<"\n"; } } } cout<<flush; return 0; }