LeetCode Weekly Contest 399 : 3165. Maximum Sum of Subsequence With Non-adjacent Elements

だいぶ典型な気はするけどな。
https://leetcode.com/problems/maximum-sum-of-subsequence-with-non-adjacent-elements/description/

問題

整数列Aが与えられる。
1要素を更新するクエリが与えられるので、その都度以下の値を求めよ。

• Aの部分列のうち、連続する要素を共に選ぶことができない場合、総和の最大値

解法

SegTreeを使い、各ノードには区間内の要素に対し

• 先頭要素を部分列に選ぶ場合/選ばない場合
• 末尾の要素を部分列に選ぶ場合/選ばない場合

の4通りの値を入れて、区間を連結していこう。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	V comp(V l,V r){
		V ret={-(1LL<<60),-(1LL<<60),-(1LL<<60),-(1LL<<60)};
		int a,b,c,d;
		FOR(a,2) FOR(b,2) FOR(c,2) FOR(d,2) {
			if(b&&c) continue;
			ret[a+d*2]=max(ret[a+d*2],l[a+b*2]+r[c+d*2]);
		}
		return ret;
		
	};
	
	SegTree_1(){
		val=vector<V>(NV*2);
		FORR(v,val) v={0,-(1LL<<40),-(1LL<<40),0};
	};
	void update(int entry, int v) {
		entry += NV;
		val[entry]={0,-(1LL<<40),-(1LL<<40),v};
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<array<ll,4>,1<<18> st;

class Solution {
public:
    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {
        int i;
        FOR(i,nums.size()) st.update(i,nums[i]);
        
        ll ret=0;
        FORR(q,queries) {
			st.update(q[0],q[1]);
			ll ma=max({st.val[1][0],st.val[1][1],st.val[1][2],st.val[1][3]});
			ret+=ma;
		}
        FOR(i,nums.size()) st.update(i,0);
		ll mo=1000000007;
		ret=ret%mo+mo;
		return ret%mo;
        
    }
};

まとめ

やっぱりちょっと変則的なSegTreeは難易度高めだね。