結果

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

ソースコード

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];
		md[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;
}
0