結果

問題 No.776 A Simple RMQ Problem
ユーザー chocorusk
提出日時 2018-12-23 09:35:03
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 797 ms / 3,000 ms
コード長 3,202 bytes
コンパイル時間 974 ms
コンパイル使用メモリ 88,024 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2024-09-25 10:28:42
合計ジャッジ時間 14,791 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
    
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
    
const int MAX_N=1<<17;
 
const ll INF=1e18;
     
ll mn[2*MAX_N-1], mx[2*MAX_N-1], md[2*MAX_N-1], part[2*MAX_N-1];
bool mada[2*MAX_N-1];
int m;
ll s[100001];
void init(int n){
    m=1;
    while(m<n) m*=2;
    for(int i=m-1; i<m-1+n; i++){
        mn[i]=s[i-m+1], mx[i]=s[i-m+1], md[i]=-INF;
    }
    for(int i=m-1+n; i<2*m-1; i++){
        mn[i]=INF, mx[i]=-INF, md[i]=-INF;
    }
    for(int k=m-2; k>=0; k--){
        mn[k]=min(mn[2*k+1], mn[2*k+2]);
        mx[k]=max(mx[2*k+1], mx[2*k+2]);
        md[k]=max({mx[2*k+2]-mn[2*k+1], md[2*k+1], md[2*k+2]});
    }
}
   
void eval(int k, int l, int r){
    if(mada[k]){
        mn[k]+=part[k];
        mx[k]+=part[k];
        if(k<m-1){
            part[2*k+1]+=part[k];
            part[2*k+2]+=part[k];
          mada[2*k+1]=1; mada[2*k+2]=1;
        }
        mada[k]=0;
      part[k]=0;
    }
}
     
void add(int a, int b, ll x, int k, int l, int r){
    eval(k, l, r);
    if(r<=a || b<=l) return;
    if(a<=l && r<=b){
        part[k]=x;
      mada[k]=1;
        eval(k, l, r);
    }else{
        add(a, b, x, k*2+1, l, (l+r)/2);
        add(a, b, x, k*2+2, (l+r)/2, r);
        mn[k]=min(mn[2*k+1], mn[2*k+2]);
        mx[k]=max(mx[2*k+1], mx[2*k+2]);
        md[k]=max({mx[2*k+2]-mn[2*k+1], md[2*k+1], md[2*k+2]});
    }
}
     
ll findmn(int a, int b, int k, int l, int r){
    eval(k, l, r);
    if(b<=l || r<=a){
        return INF;
    }
    if(a<=l && r<=b){
        return mn[k];
    }else{
        return min(findmn(a, b, 2*k+1, l, (l+r)/2), findmn(a, b, 2*k+2, (l+r)/2, r));
    }
}
    
ll findmx(int a, int b, int k, int l, int r){
    eval(k, l, r);
    if(b<=l || r<=a){
        return -INF;
    }
    if(a<=l && r<=b){
        return mx[k];
    }else{
        return max(findmx(a, b, 2*k+1, l, (l+r)/2), findmx(a, b, 2*k+2, (l+r)/2, r));
    }
}
ll findmd(int a, int b, int k, int l, int r){
    eval(k, l, r);
    if(b<=l || r<=a){
        return -INF;
    }
    if(a<=l && r<=b){
        return md[k];
    }else{
        return max({findmd(a, b, 2*k+1, l, (l+r)/2), findmd(a, b, 2*k+2, (l+r)/2, r), findmx(a, b, 2*k+2, (l+r)/2, r)-findmn(a, b, 2*k+1, l, (l+r)/2
            )});
    }
}
int main()
{
    int n, q;
    cin>>n>>q;
    ll a[100001];
    for(int i=1; i<=n; i++){
        cin>>a[i]; s[i]=s[i-1]+a[i];
    }
    init(n+1);
    for(int i=0; i<q; i++){
        string t;
        cin>>t;
        if(t=="set"){
            int i; ll x; cin>>i>>x;
            ll d=x-a[i];
            add(i, n+1, d, 0, 0, m);
            a[i]=x;
        }else{
            int l1, l2, r1, r2;
            cin>>l1>>l2>>r1>>r2;
            l1--; l2--;
            if(l2<r1){
                cout<<findmx(r1, r2+1, 0, 0, m)-findmn(l1, l2+1, 0, 0, m)<<endl;
            }else{
                ll ans=-INF;
                if(l2<r2){
                    ans=max(ans, findmx(l2+1, r2+1, 0, 0, m)-findmn(l1, l2+1, 0, 0, m));
                }
                if(l1<r1){
                    ans=max(ans, findmx(r1, r2+1, 0, 0, m)-findmn(l1, r1, 0, 0, m));
                }
                l1=max(l1, r1), l2=min(l2, r2);
                ans=max(ans, findmd(l1, l2+1, 0, 0, m));
                cout<<ans<<endl;
            }
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0