AtCoder ABC #368 (日立ヴァンタラプログラミングコンテスト2024) : G - Add and Multiply Queries

この類の解法テク、Codeforcesに多いイメージ。
https://atcoder.jp/contests/abc368/tasks/abc368_g

問題

整数列A,Bに対し、以下のクエリに答えよ。

• Aを1点更新する
• Bを1点更新する
• 区間[L,R]が指定される。変数v=0に対し、i=L～Rに対しvを以下のいずれかで更新する。
  • v+=A[i], v*=B[i]
  • vの最大値を求めよ。なお、その値は10^18以下であることが保証される。

解法

A,Bは正なのと、3つ目のクエリの条件より、区間内にB[i]が2以上な物は高々log(10^18)個程度しかない。
B[i]=1の部分は、v+=A[i]をした方が良いのは明らか。

よって各クエリに対し、B[i]=1の部分はBITを使ってA[i]の和を一気に加算し、B[i]＞1のところだけ加算と乗算どちらを取るか両方試していこう。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt;

int N;
map<int,int> M;
int A[202020],B[202020];
int Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		bt.add(i+1,A[i]);
	}
	FOR(i,N) {
		cin>>B[i];
		if(B[i]>1) M[i+1]=B[i];
	}
	
	cin>>Q;
	while(Q--) {
		cin>>i>>x>>y;
		if(i==1) {
			x--;
			bt.add(x+1,-A[x]);
			A[x]=y;
			bt.add(x+1,A[x]);
		}
		else if(i==2) {
			x--;
			M.erase(x+1);
			B[x]=y;
			if(y>1) M[x+1]=y;
		}
		else {
			vector<int> V;
			auto it=M.lower_bound(x);
			while(it!=M.end()&&it->first<=y) {
				V.push_back(it->first);
				it++;
			}
			ll cur=0;
			int pre=x-1;
			FORR(v,V) {
				cur+=bt(v-1)-bt(pre);
				cur=max(cur+A[v-1],cur*B[v-1]);
				pre=v;
			}
			if(pre<y) cur+=bt(y)-bt(pre);
			cout<<cur<<endl;
		}
	}
}

まとめ

もう少し難易度が高いと、Aに0が混ざってたりするよね。