結果
問題 | No.776 A Simple RMQ Problem |
ユーザー |
![]() |
提出日時 | 2019-12-03 18:06:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 414 ms / 3,000 ms |
コード長 | 2,963 bytes |
コンパイル時間 | 942 ms |
コンパイル使用メモリ | 97,580 KB |
最終ジャッジ日時 | 2025-01-08 07:15:40 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include <iostream>#include <vector>#include <climits>#include <functional>#include <algorithm>using namespace std;using ll = long long;template<class T> using vec = vector<T>;template<class T> using vvec = vector<vec<T>>;template<typename Monoid>class SegmentTree{private:using F = function<Monoid(Monoid&,Monoid&)>;int sz;vector<Monoid> seg;const F op;//演算const Monoid e;//単位元public:SegmentTree(int n,const F op,const Monoid &e):op(op),e(e){sz = 1;while(sz<n) sz <<= 1;seg.assign(2*sz,e);}//代入void set(int k, const Monoid &x){seg[k+sz] = x;}//前計算(?)void build(){for(int i=sz-1;i>0;i--){seg[i] = op(seg[2*i],seg[2*i+1]);}}void update(int k,const Monoid &x){k += sz;seg[k] = x;while(k>>=1){seg[k] = op(seg[2*k],seg[2*k+1]);}}Monoid query(int l,int r){Monoid L = e,R = e;for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){if(l&1) L = op(L,seg[l++]);if(r&1) R = op(seg[--r],R);}return op(L,R);}Monoid operator[](const int &k)const{return seg[k+sz];}};struct state{ll sum,lsum,rsum,ma;};constexpr ll inf = 1e18;state op(state& l,state& r){ll sum,lsum,rsum,ma;sum = l.sum+r.sum;lsum = max(l.lsum,l.sum+r.lsum);rsum = max(r.rsum,r.sum+l.rsum);ma = max(max(l.ma,r.ma),l.rsum+r.lsum);return (state){sum,lsum,rsum,ma};}int main(){int N,Q;cin >> N >> Q;SegmentTree<state> seg(N,op,(state){0,-inf,-inf,-inf});for(int i=0;i<N;i++){ll a;cin >> a;seg.set(i,(state){a,a,a,a});}seg.build();for(int i=0;i<Q;i++){string S;cin >> S;if(S=="set"){int id; ll val;cin >> id >> val;id--;seg.update(id,(state){val,val,val,val});}else{vec<int> L(2),R(2);cin >> L[0] >> L[1] >> R[0] >> R[1];L[0]--; L[1]--; R[0]--; R[1]--;if(L[1]<R[0]){cout << seg.query(L[0],L[1]+1).rsum+seg.query(L[1]+1,R[0]).sum+seg.query(R[0],R[1]+1).lsum << endl;}else if(L[0]<=R[0] && R[1]<=L[1]){cout << max(seg.query(L[0],R[0]).rsum+seg.query(R[0],R[1]+1).lsum,seg.query(R[0],R[1]+1).ma) << endl;}else if(R[0]<=L[0] && L[1]<=R[1]){cout << max(seg.query(L[0],L[1]+1).ma,seg.query(L[0],L[1]+1).rsum+seg.query(L[1]+1,R[1]+1).lsum) << endl;}else if(R[0]<=L[0]){cout << seg.query(L[0],R[1]+1).ma << endl;}else{cout << max({seg.query(L[0],R[0]).rsum+seg.query(R[0],R[1]+1).lsum,seg.query(L[0],L[1]+1).rsum+seg.query(L[1]+1,R[1]+1).lsum,seg.query(R[0],L[1]+1).ma}) << endl;}}}}