https://atcoder.jp/contests/abc368/submissions/57169581

#include<bits/stdc++.h>
using namespace std;
long long s[200005],a[200005],b[200005],n,x,q,op,p,l,r,su=0,sum=0;
void update(int k,long long x){while(k<=n)s[k]+=x,k+=k&-k;}
void query(int k,long long &ans){ans=0;while(k)ans+=s[k],k-=k&-k;}
int32_t main(){
	cin>>n;set<int> st;
	for(int i=1;i<=n;++i)cin>>a[i],update(i,a[i]);
	for(int i=1;i<=n;++i){cin>>b[i];if(b[i]!=1)st.insert(i);}
	cin>>q;
	while(q--){
		cin>>op;if(op==1)cin>>p>>x,update(p,x-a[p]),a[p]=x;
		if(op==2){cin>>p>>x;if(b[p]!=1)st.erase(p);b[p]=x;if(b[p]!=1)st.insert(p);}
		if(op==3){cin>>l>>r;long long ans=a[l++];while(l<=r){p=*st.lower_bound(l);query(min(p-1,r),sum);query(l-1,su);ans+=sum-su;if(p>r)break;ans=max(ans*b[p],ans+a[p]);l=p+1;}cout<<ans<<'\n';}
	}
}