前言
最简单的一次，终于 AK 了 ABC，纪念一下。
思路
看到题目中有一句加粗的话
入力で与えられるタイプ $ 3 $ のクエリの答えは $ 10^{18} $ 以下であることが保証されています。
翻译出来是对于所有操作 \(3\)，答案不超过 \(10^{18}\)。
首先，\(a_i\) 一定不会是 \(0\)，考虑一种情况，先加 \(a_l\)，然后一直乘 \(b_i\)，如果答案不超过 \(10^{18}\)，那么有意义，也就是不等于 \(1\) 的 \(b_i\) 在 \(l\) 到 \(r\) 中应该是很少的，只有 \(60\) 个左右。
用平衡树维护 \(b_i>1\) 的位置，用线段树维护 \(a\)，实现区间求和和单点修改。
查询的时候，\(b_i>1\) 的位置判断 \(v \times b_i\) 和 \(v+a_i\) 哪个更大，就选哪个。剩下的就是一段一段的区间，把这些区间所有的 \(a_i\) 都加起来就可以了。
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cout<<#x<<':'<<x<<endl
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e5+5;
int n,m;
int a[N],b[N];
int tree[N<<2];
#define ls p<<1
#define rs p<<1|1
void push_up(int p){
tree[p]=tree[ls]+tree[rs];
}
void build(int p,int l,int r){
if(l==r){
tree[p]=a[l];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
push_up(p);
}
void change(int p,int l,int r,int x,int v){
if(l==r){
tree[p]=v;
return;
}int mid=(l+r)>>1;
if(x<=mid) change(ls,l,mid,x,v);
else change(rs,mid+1,r,x,v);
push_up(p);
}
int ask(int p,int l,int r,int ql,int qr){
if(ql>qr) return 0;
if(ql<=l&&r<=qr){
return tree[p];
}int mid=(l+r)>>1,res=0;
if(ql<=mid) res+=ask(ls,l,mid,ql,qr);
if(qr>mid) res+=ask(rs,mid+1,r,ql,qr);
return res;
}
int ch[N][2],val[N],key[N],siz[N],top,x,y,z,root;
void update(int x){siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];}
int new_node(int v){siz[++top]=1;val[top]=v;key[top]=rand();return top;}
int merge(int x,int y){
if(!x||!y) return x+y;
if(key[x]<key[y]){
ch[x][1]=merge(ch[x][1],y);
update(x);
return x;
}
else{
ch[y][0]=merge(x,ch[y][0]);
update(y);
return y;
}
}
void split(int now,int k,int &x,int &y){
if(!now) x=y=0;
else{
if(val[now]<=k)x=now,split(ch[now][1],k,ch[now][1],y);
else y=now,split(ch[now][0],k,x,ch[now][0]);
update(now);
}
}
int kth(int now,int k){
while(true){
if(k<=siz[ch[now][0]])now=ch[now][0];
else if(k==siz[ch[now][0]]+1)return now;
else k-=siz[ch[now][0]]+1,now=ch[now][1];
}
}
void insert(int a){
split(root,a,x,y);
root=merge(merge(x,new_node(a)),y);
}
void del(int a){
split(root,a,x,z);
split(x,a-1,x,y);
y=merge(ch[y][0],ch[y][1]);
root=merge(merge(x,y),z);
}
int nxt(int a){
split(root,a,x,y);
int ans=val[kth(y,1)];
root=merge(x,y);
return ans;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
for(int i=1;i<=n;i++){
cin>>b[i];
if(b[i]>1) insert(i);
}
cin>>m;
for(int i=1,op,l,r;i<=m;i++){
cin>>op>>l>>r;
if(op==1) change(1,1,n,l,r),a[l]=r;
if(op==2){
if(b[l]==1&&r>1) insert(l);
else if(b[l]>1&&r==1) del(l);
b[l]=r;
}
if(op==3){
int ans=a[l],p=l+1;
while(nxt(l)<=r&&nxt(l)!=0) {
l=nxt(l);
ans+=ask(1,1,n,p,l-1);
if(ans*b[l]>ans+a[l]) ans*=b[l];
else ans+=a[l];
p=l+1;
}
if(l<=r) ans+=ask(1,1,n,l+1,r);
cout<<ans<<endl;
}
}
return 0;
}