結果
問題 | No.1234 典型RMQ |
ユーザー |
|
提出日時 | 2020-09-18 21:38:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 366 ms / 2,000 ms |
コード長 | 2,177 bytes |
コンパイル時間 | 1,238 ms |
コンパイル使用メモリ | 85,764 KB |
実行使用メモリ | 8,192 KB |
最終ジャッジ日時 | 2024-11-09 01:45:09 |
合計ジャッジ時間 | 9,408 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
コンパイルメッセージ
main.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 77 | main() | ^~~~
ソースコード
#include<iostream> using namespace std; #include<vector> #include<functional> template<typename T> struct lazysegtree{ using F=function<T(T,T)>; using G=function<T(T,T,int,int)>; const F calcfn,lazycalcfn; const G updatefn; int n; T defvalue; vector<T>dat,lazy; vector<bool>lazyflag; lazysegtree(int n_=0,T defvalue_=0, const F calcfn_=[](T a,T b){return a+b;}, const F lazycalcfn_=[](T a,T b){return a+b;}, const G updatefn_=[](T a,T b,int l,int r){return a+b*(r-l);} ):defvalue(defvalue_), calcfn(calcfn_),lazycalcfn(lazycalcfn_),updatefn(updatefn_) { n=1; while(n<n_)n<<=1; dat.assign(2*n-1,defvalue); lazy.assign(2*n-1,T()); lazyflag.assign(2*n-1,false); } void copy(const vector<T>&v) { for(int i=0;i<v.size();i++)dat[i+n-1]=v[i]; for(int i=n-2;i>=0;i--)dat[i]=calcfn(dat[2*i+1],dat[2*i+2]); } void eval(int i,int l,int r) { if(lazyflag[i]) { dat[i]=updatefn(dat[i],lazy[i],l,r); if(r-l>1) { lazy[2*i+1]=lazyflag[2*i+1]?lazycalcfn(lazy[2*i+1],lazy[i]):lazy[i]; lazy[2*i+2]=lazyflag[2*i+2]?lazycalcfn(lazy[2*i+2],lazy[i]):lazy[i]; lazyflag[2*i+1]=lazyflag[2*i+2]=true; } lazyflag[i]=false; } } void update(int a,int b,T x,int k=0,int l=0,int r=-1)//[a,b) { if(r<0)r=n; eval(k,l,r); if(b<=l||r<=a)return; else if(a<=l&&r<=b) { lazy[k]=lazyflag[k]?lazycalcfn(lazy[k],x):x; lazyflag[k]=true; eval(k,l,r); } else { update(a,b,x,2*k+1,l,(l+r)/2); update(a,b,x,2*k+2,(l+r)/2,r); dat[k]=calcfn(dat[2*k+1],dat[2*k+2]); } } T query(int a,int b,int k=0,int l=0,int r=-1)//[a,b) { if(r<0)r=n; eval(k,l,r); if(b<=l||r<=a)return defvalue; else if(a<=l&&r<=b)return dat[k]; else return calcfn( query(a,b,2*k+1,l,(l+r)/2), query(a,b,2*k+2,(l+r)/2,r) ); } }; main() { int N; cin>>N; vector<long>A(N); for(int i=0;i<N;i++)cin>>A[i]; lazysegtree<long>P(N,(long)9e18, [](long a,long b){return a<b?a:b;}, [](long a,long b){return a+b;}, [](long a,long b,int l,int r){return a+b;}); P.copy(A); int Q; cin>>Q; for(;Q--;) { int k,l,r,c;cin>>k>>l>>r>>c; if(k==1) { P.update(l-1,r,c); } else { cout<<P.query(l-1,r)<<endl; } } }