Add and Multiply Queries

题目链接：G - Add and Multiply Queries

区间修改+区间查询可以用线段树来做，但是这边介绍树状数组的写法。首先将a数组和b数组分开考虑，对于a数组，因为是加法运算求区间和，因此我们可以采用树状数组+差分来写，对于数组b，我们已知如果b[i] =  1 ，那么不如就进行加法运算，所以我们把b数组中大于1的数加入到一个set集合中，记住set记录的是位置，不是数值，然后可以二分查找进行运算。

代码：
 

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5+5;
int a[N],b[N],tr[N];
int n,q;
set<int>st;

int lowbit(int x){
    return x&(-x);
}

void add(int x,int c){
    for(int i=x;i<=n;i+=lowbit(i)){
        tr[i] += c;
    }
    return;
}

int ask(int x){
    int res = 0;
    for(int i=x;i>=1;i-=lowbit(i)){
        res += tr[i];
    }
    return res;
}

int find(int x){
    return *st.upper_bound(x);
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        add(i,a[i]);
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        if(b[i]>1)st.insert(i);
    }
    st.insert(n+1);
    cin>>q;

    while(q--){
        int op;cin>>op;
        if(op==1){
            int x,k;cin>>x>>k;
            add(x,-a[x]);
            add(x,k);
            a[x] = k;
        }
        else if(op==2){
            int x,k;cin>>x>>k;
            if(b[x]==1&&k>1)st.insert(x);
            if(k==1&&b[x]>1)st.erase(x);
            b[x] = k;
        }
        else{
            int l,r;cin>>l>>r;
            int p = l-1;
            int ans = 0;
            while(p<r){
                int t = find(p);
                if(t>r){
                    ans += ask(r)-ask(p);
                    break;
                } 
                ans += ask(t-1)-ask(p);
                if(ans+a[t]>ans*b[t])ans+=a[t];
                else ans*=b[t];
                p = t;
            }
            cout<<ans<<"\n";
        }
    }


}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    while(T--){
        solve();
    }

    return 0;
}