結果

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

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;
#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------
template<class V,int NV> class SegTree_1 {
public:
    vector<V> sum;
    vector<V> ma;
    vector<V> Lma;
    vector<V> Rma;
    
    SegTree_1(){
        Lma=Rma=ma=sum=vector<V>(NV*2,-1LL<<50);
    };
    vector<V> getmax(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
        if(r<=x || y<=l) return {0,-(1LL<<60),-(1LL<<60),-(1LL<<60)};
        if(x<=l && r<=y) return {sum[k],Lma[k],Rma[k],ma[k]};
        
        auto a=getmax(x,y,l,(l+r)/2,k*2);
        auto b=getmax(x,y,(l+r)/2,r,k*2+1);
        if(a[1]<=-(1LL<<50)) return b;
        if(b[1]<=-(1LL<<50)) return a;
        vector<V> c(4);
        c[0]=a[0]+b[0];
        c[1]=max({a[1],a[0],a[0]+b[1]});
        c[2]=max({b[2],b[0],a[2]+b[0]});
        c[3]=max({a[3],b[3],a[1],a[2],b[1],b[2],a[2]+b[1]});
        
        return c;
    }
    
    void update(int entry, V v) {
        entry += NV;
        sum[entry]=ma[entry]=Lma[entry]=Rma[entry]=v;
        
        while(entry>1) {
            entry>>=1;
            sum[entry]=sum[entry*2]+sum[entry*2+1];
            Lma[entry]=max({Lma[entry*2],sum[entry*2]+Lma[entry*2+1],sum[entry*2]});
            Rma[entry]=max({Rma[entry*2]+sum[entry*2+1],sum[entry*2+1],Rma[entry*2+1]});
            ma[entry]=max({ma[entry*2],ma[entry*2+1],Rma[entry*2]+Lma[entry*2+1],Lma[entry*2],Rma[entry*2],Lma[entry*2+1],Rma[entry*2+1]});
            
        }
    }
};
int N,Q;
ll A[101010];
SegTree_1<ll,1<<18> st;
void solve() {
    int i,j,k,l,r,x,y; string s;
    
    cin>>N>>Q;
    FOR(i,N) {
        cin>>A[i+1];
        st.update(i+1,A[i+1]);
    }
    
    while(Q--) {
        cin>>s;
        if(s=="set") {
            cin>>i>>x;
            A[i]=x;
            st.update(i,x);
        }
        else {
            int L1,L2,R1,R2;
            cin>>L1>>L2>>R1>>R2;
            R1=max(L1,R1);
            L2=min(L2,R2);
            
            ll ret=-1LL<<60;
            if(L2<=R1) {
                auto b=st.getmax(L1,L2+1);
                auto c=st.getmax(L2,R1+1);
                auto d=st.getmax(R1,R2+1);
                ret=max(ret,b[2]+c[0]+d[1]-A[L2]-A[R1]);
            }
            else {
                {
                    auto b=st.getmax(L1,R1+1);
                    auto c=st.getmax(R1,R2+1);
                    ret=max(ret,b[2]+c[1]-A[R1]);
                }
                {
                    auto b=st.getmax(L1,L2+1);
                    auto c=st.getmax(L2,R2+1);
                    ret=max(ret,b[2]+c[1]-A[L2]);
                }
                {
                    auto b=st.getmax(R1,L2+1);
                    ret=max(ret,b[3]);
                }
            }
            
            cout<<ret<<endl;
        }
    }
    
    
}
int main(int argc,char** argv){
    string s;int i;
    if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
    FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
    cout.tie(0); solve(); return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0