Hello 2024 : F2. Wine Factory (Hard Version)

解き切れてよかったね。
https://codeforces.com/contest/1919/problem/F2

問題

N要素の整数列A,Bと、(N-1)要素の整数列Cが与えられる。
N個のタンクがありそれぞれ容量A[i]の水が入っている。
また、各タンクでは最大B[i]まで、入っている水をワインに変えることができる。
もしタンクにワインに仕切れない水が残っている場合、i番からi+1番のタンクに水を移せるが、その量はC[i]までとなる。

A,B,Cを更新するクエリが与えられる。
適宜、ワインにできる最大容量を答えよ。

解法

SegTreeで、各ワインタンク列について、受け入れによって追加できるワイン量、次のタンクに流せるワイン量、生成が確定しているワイン量を持ち更新していこう。

int N,Q;
ll A[505050],B[505050],C[505050];


template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	V comp(V l,V r){
		ll x=min(l[2],r[1]);
		l[2]-=x;
		r[1]-=x;
		ll a=l[0]+r[0]+x;
		ll b=l[1]+min(r[1],l[3]);
		ll c=r[2]+min(l[2],r[3]);
		ll d=min(r[3]-min(l[2],r[3]),l[3]-min(r[1],l[3]));
		
		return {a,b,c,d};
	};
	
	SegTree_1(){val=vector<V>(NV*2,{0,0,0,0});};
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v; //上書きかチェック
		while(entry>1) {
			entry>>=1;
			val[entry]=comp(val[entry*2],val[entry*2+1]);
		}
	}
};
SegTree_1<array<ll,4>,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	ll S=0;
	FOR(i,N) {
		cin>>A[i];
	}
	FOR(i,N) cin>>B[i];
	FOR(i,N-1) cin>>C[i];
	C[N-1]=1LL<<60;
	FOR(i,N) {
		if(A[i]<B[i]) st.update(i,{min(A[i],B[i]),B[i]-A[i],0LL,C[i]});
		else st.update(i,{min(A[i],B[i]),0LL,min(A[i]-B[i],C[i]),C[i]-min(A[i]-B[i],C[i])});
	}
	
	while(Q--) {
		int P,X,Y;
		ll Z;
		cin>>P>>X>>Y>>Z;
		P--;
		A[P]=X;
		B[P]=Y;
		C[P]=Z;
		if(P==N-1) C[P]=1LL<<60;
		i=P;
		if(A[i]<B[i]) st.update(i,{min(A[i],B[i]),B[i]-A[i],0LL,C[i]});
		else st.update(i,{min(A[i],B[i]),0LL,min(A[i]-B[i],C[i]),C[i]-min(A[i]-B[i],C[i])});
		cout<<st.val[1][0]<<endl;
	}
	
}

まとめ

SegTreeで管理することさえ思いついてしまえば、あとは簡単。