結果

問題 No.776 A Simple RMQ Problem
コンテスト
ユーザー hashiryo
提出日時 2019-06-04 13:38:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 318 ms / 3,000 ms
コード長 3,217 bytes
コンパイル時間 1,813 ms
コンパイル使用メモリ 176,156 KB
実行使用メモリ 12,288 KB
最終ジャッジ日時 2024-09-17 20:46:50
合計ジャッジ時間 8,502 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long RmaxsumQ::T = 0; (RmaxsumQ::T) < (n); ++ (RmaxsumQ::T)) cerr << #x << "[" << RmaxsumQ::T << "]: " << x[RmaxsumQ::T] << '\n'
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll> Pll;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/10;
const ll MOD = 1e9+7;

template <typename M>
struct SegmentTree{
    using T = typename M::T;
    int n;
    vector<T> dat;
    SegmentTree(){}
    SegmentTree(int n_){init(n_);}
    SegmentTree(const vector<T> &v){build(v);}
    void init(int n_){
        n=1;
        while(n<n_) n<<=1;
        dat.assign(n<<1,M::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]=M::f(dat[(i<<1)|0],dat[(i<<1)|1]);
    }
    void set_val(int k,T x){
        dat[k+=n]=x;
        while(k>>=1)
            dat[k]=M::f(dat[(k<<1)|0],dat[(k<<1)|1]);
    }
    //[a,b)
    T query(int a,int b,int k=1,int l=0,int r=-1){
        if(r<0)r=n;
        if(r<=a||b<=l) return M::ti();
        if(a<=l&&r<=b) return dat[k];
        T vl=query(a,b,k*2,l,(l+r)/2);
        T vr=query(a,b,k*2+1,(l+r)/2,r);
        return M::f(vl,vr);
    }
    T operator[](const int &k) const {return dat[k + n];}
};

struct RmaxsumQ{
    struct T{
      ll sum,max,l,r;
      T(){}
      T(ll a,ll b,ll c,ll d):sum(a),max(b),l(c),r(d){}
    };
    static T ti(){return T(0,-INF,-INF,-INF);}
    static T f(const T& a, const T & b){
        T ret;
        ret.sum = a.sum+b.sum;
        ret.max = max({a.max,b.max,a.r+b.l});
        ret.l = max(a.l,a.sum+b.l);
        ret.r = max(a.r+b.sum,b.r);
        return ret;
    }
};
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N,Q;cin>>N>>Q;
  SegmentTree<RmaxsumQ> seg(N);
  vll a(N);
  for(ll i=0;i<N;i++){
    cin>>a[i];
    seg.set_val(i,{a[i],a[i],a[i],a[i]});
  }
  for(ll q=0;q<Q;q++){
    string op;cin>>op;
    if(op[0]=='s'){
      ll i,x;cin>>i>>x;i--;
      seg.set_val(i,{x,x,x,x});
      a[i]=x;
    }else{
      ll l1,l2,r1,r2;cin>>l1>>l2>>r1>>r2;
      l1--;l2--;r1--;r2--;
      ll ans=0;
      if(l2<r1){
        RmaxsumQ::T l=seg.query(l1,l2+1);
        RmaxsumQ::T m=seg.query(l2+1,r1);
        RmaxsumQ::T r=seg.query(r1,r2+1);
        ans = l.r+m.sum+r.l;
      }else if(r1<=l1){
        if(l2<=r2){
          RmaxsumQ::T m=seg.query(l1,l2+1);
          RmaxsumQ::T r=seg.query(l2,r2+1);
          ans = max(m.max,m.r+r.l-a[l2]);
        }else{
          RmaxsumQ::T m=seg.query(l1,r2+1);
          ans = m.max;
        }
      }else{
        if(r2<=l2){
          RmaxsumQ::T l=seg.query(l1,r1+1);
          RmaxsumQ::T m=seg.query(r1,r2+1);
          ans = max(m.max,l.r+m.l-a[r1]);
        }else{
          RmaxsumQ::T l=seg.query(l1,r1+1);
          RmaxsumQ::T m=seg.query(r1,l2+1);
          RmaxsumQ::T r=seg.query(l2,r2+1);
          ans = m.max;
          ans = max(ans,l.r+m.l-a[r1]);
          ans = max(ans,m.r+r.l-a[l2]);
          ans = max(ans,l.r+m.sum+r.l-a[r1]-a[l2]);
        }
      }
      cout<<ans<<endl;
    }
  }
  return 0;
}
0