思路
可以观察到一件事情：在两个港口之间的船他们对应的价值都是一样的，都为左边港口的权值。因此对于这段区间的价值和就可以写成 \(val \times \sum dis\) 的形式，\(\sum dis\) 便为这些船到右边港口的距离和。那么我们就可以按照港口把序列分成很多个区间来考虑。
港口用一个 set 维护，这样能很方便的插入以及找前驱后继。每次插入一个新港口时，设它左边第一个港口在 \(l\)，右边第一个在 \(r\)，他自己在 \(now\)。\(now\) 就把 \(l,r\) 分成了两个新的区间，我们就需要进行区间修改，不难想到用线段树维护，维护的值就是一段区间的 \(val,\sum dis\) 以及整个区间的答案。对于 \((now,r]\) 这个区间，他们的 \(\sum dis\) 没有改变，只是 \(val\) 变成了新输入的 \(v\)，用懒标记区间赋值 \(val\) 即可。对于 \([l,now)\) 改变的就是 \(\sum dis\)，但是因为有一个 \(\sum\)，不能区间推平了，必须换个角度思考。把 \(\sum dis\) 拆成每个点单独的 \(dis\)，一开始是每个点到 \(r\) 的距离，现在变成了每个点到 \(now\) 的距离，减少的就是 \(r-now\)！于是把区间中的所有点都减去一个 \(r-now\)，相当于 \(\sum dis\) 减去了 \(len \times (r-now)\)，把 \(r-now\) 用懒标记记录下来，这是可以下传的，就维护好了。至于 \([now,now]\) 这个点，全部变成 \(0\) 即可。
pushup 把左右儿子的 \(dis\) 都加起来，\(val\) 赋为左儿子的 \(val\)，区间答案直接 \(\sum dis \times val\)（我们只考虑每两个港口间的区间，不考虑跨区间的东西，因此可以直接用这个式子算答案）。
code
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ls p<<1
#define rs p<<1|1
using namespace std;
int t;
const int N=3e5+5;
int n,m,q;
ll val[N],x[N];
set<ll>s;//维护港口
struct Tree{
int l,r;
ll sum;
ll dis,val;
ll ad,vl; //ad dis的懒标记，vl val的懒标记
}tr[N<<4];
inline void pushup(int p){
tr[p].dis=tr[ls].dis+tr[rs].dis;
tr[p].val=tr[ls].val;
tr[p].sum=tr[ls].sum+tr[rs].sum;
}
inline void pushdown(int p){
if(!tr[p].ad && !tr[p].vl)return;
ll ds=tr[p].ad,vl=tr[p].vl;
if(vl)tr[ls].val=vl,tr[rs].val=vl;
tr[ls].dis-=(tr[ls].r-tr[ls].l+1)*ds;
tr[rs].dis-=(tr[rs].r-tr[rs].l+1)*ds;
tr[ls].sum=tr[ls].val*tr[ls].dis;
tr[rs].sum=tr[rs].val*tr[rs].dis;
tr[ls].ad+=ds;tr[rs].ad+=ds;
if(vl)tr[ls].vl=vl,tr[rs].vl=vl;
tr[p].ad=0;tr[p].vl=0;
}
void build(int p,int l,int r){
tr[p].l=l;tr[p].r=r;
if(l==r){
auto nxt=s.lower_bound(l);//后继
if((*nxt)==l)return;
auto now=nxt;
now--;
tr[p].val=val[*now];
tr[p].dis=(*nxt)-l;
tr[p].sum=tr[p].val*tr[p].dis;
return;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(p);
}
void updatedis(int p,int l,int r,ll d){
if(tr[p].l>=l&&tr[p].r<=r){
tr[p].dis-=(tr[p].r-tr[p].l+1)*d;
tr[p].sum=tr[p].dis*tr[p].val;
tr[p].ad+=d;
return;
}
pushdown(p);
int mid=tr[p].l+tr[p].r>>1;
if(l<=mid)updatedis(ls,l,r,d);
if(r>mid)updatedis(rs,l,r,d);
pushup(p);
}
void updateval(int p,int l,int r,ll d){
if(tr[p].l>=l&&tr[p].r<=r){
tr[p].val=d;
tr[p].vl=d;
tr[p].sum=tr[p].dis*tr[p].val;
return;
}
pushdown(p);
int mid=tr[p].l+tr[p].r>>1;
if(l<=mid)updateval(ls,l,r,d);
if(r>mid)updateval(rs,l,r,d);
pushup(p);
}
ll query(int p,int l,int r){
if(tr[p].l>=l&&tr[p].r<=r)return tr[p].sum;
pushdown(p);
int mid=tr[p].l+tr[p].r>>1;
ll res=0;
if(l<=mid)res+=query(ls,l,r);
if(r>mid)res+=query(rs,l,r);
return res;
}
void modify(int p,int x){
if(tr[p].l==tr[p].r){
tr[p].dis=tr[p].val=tr[p].ad=tr[p].vl=tr[p].sum=tr[p].val=0;
return;
}
int mid=tr[p].l+tr[p].r>>1;
if(x<=mid)modify(ls,x);
else modify(rs,x);
pushup(p);
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=m;++i)cin>>x[i],s.insert(x[i]);
for(int i=1;i<=m;++i)cin>>val[x[i]];
build(1,1,n);
while(q--){
int op;
ll l,r;
cin>>op>>l>>r;
if(op==1){
s.insert(l);val[l]=r;
auto pos=s.find(l);
auto pre=pos,nxt=pos;
pre--;nxt++;
ll prex=*pre;
ll nxtx=*nxt;
if(prex+1<l)updatedis(1,prex+1,l-1,(nxtx-l)); //更新左区间的dis
if(l+1<nxtx)updateval(1,l+1,nxtx-1,r);//右区间的val
modify(1,l);
}
else cout<<query(1,l,r)<<endl;
}
return 0;
}