yukicoder : No.776 A Simple RMQ Problem

典型だけど手間のかかる問題。
https://yukicoder.me/problems/no/776

問題

数列Aに対し、以下のクエリを順次処理せよ。

• 指定された要素の値を更新する。
• 2つの区間[L1,L2]および[R1,R2]が与えられる。L∈[L1,L2]かつR∈[R1,R2]である(L,R)の対のうち、sum(A[L...R])の最大値を求めよ。

解法

SegTreeでとく。
各要素には以下の４値を持たせる。

• 区間内の値の総和
• 区間内のうち、部分列の総和の最大値
• 区間内のうち、左端要素を含む部分列の総和の最大値
• 区間内のうち、右端要素を含む部分列の総和の最大値

更新クエリはそれぞれ上記４値を更新するだけ。

• L2≦R1の場合
  • A[L2...R1]は必ず解となる区間に含まなければならない。
  • よって、A[(L2+1)...(R1-1)]の総和に以下の２値を加える。
    • A[L2]を右端とし、左端を[L1,L2]の範囲とする部分列の最大値
    • A[R1]を左端とし、右端を[R1,R2]の範囲とする部分列の最大値

• R1＜L2の場合も、以下の最大値を求めればよい。
  • A[R1]を含むケース(上記同様に左右にどこまで伸ばせるか求める)
  • A[L2]を含むケース(上記同様に左右にどこまで伸ばせるか求める)
  • A[(R1+1)...(L2-1)]内の最大値

template<class V,int NV> class SegTree_1 {
public:
	vector<V> sum,ma,Lma,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;
		}
	}
	
	
}
||<<

*まとめ