题面
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define fi first
#define se second
#define push_back pb
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define int long long
#define N 300100
#define ls i<<1
#define rs i<<1|1
#define mid (l+r)/2
struct Seg_Tree{
ll sum[N<<3],lz1[N<<3],a[N<<3],lz2[N<<3],sum1[N<<3];
// 这里 N*8 要特别注意,因为后续会先 pushdown() 所以多乘了个 2.
void pu(int i){
sum[i]=sum[ls]+sum[rs];
sum1[i]=sum1[ls]+sum1[rs];
}
void build(int i,int l,int r){
if(l==r){
sum[i]=lz1[i]=lz2[i]=a[i]=sum1[i]=0;
return;
}
build(ls,l,mid),build(rs,mid+1,r);
pu(i);
}
void pd(int i,int l,int r){
if(lz1[i]){
sum[ls]=1ll*(mid-l+1)*lz1[i];
sum[rs]=1ll*(r-mid)*lz1[i];
lz1[ls]=lz1[i],lz1[rs]=lz1[i];
}
if(lz2[i]){
sum1[ls]=lz2[i]*(mid-l+1)*(l+mid)/2;
sum1[rs]=lz2[i]*(r-mid)*(mid+1+r)/2;
lz2[ls]=lz2[rs]=lz2[i];
}
lz1[i]=0,lz2[i]=0;
}
void mod1(int i,int l,int r,int cl,int cr,ll k){
pd(i,l,r);
if(l>=cl&&r<=cr){
sum[i]=(r-l+1)*k;
lz1[i]=k;
return;
}
if(r<cl||l>cr) return;
mod1(ls,l,mid,cl,cr,k);
mod1(rs,mid+1,r,cl,cr,k);
pu(i);
}
void mod2(int i,int l,int r,int cl,int cr,ll k){
pd(i,l,r);
if(l>=cl&&r<=cr){
sum1[i]=1ll*(r-l+1)*(l+r)/2*k;
lz2[i]=k;
return;
}
if(r<cl||l>cr) return;
mod2(ls,l,mid,cl,cr,k);
mod2(rs,mid+1,r,cl,cr,k);
pu(i);
}
ll ask(int i,int l,int r,int cl,int cr){
//cout<<l<<" "<<r<<" "<<sum[i]<<" "<<sum1[i]<<endl;
pd(i,l,r); ll ans=0;
if(l>=cl&&r<=cr) ans+=sum[i]-sum1[i];
else if(r<cl||l>cr) ans+=0;
else{
ans+=ask(ls,l,mid,cl,cr);
ans+=ask(rs,mid+1,r,cl,cr);
}
pu(i);
return ans;
}
} t;
int n,m,q;
set<int> s;
int v[N];
signed main(){
IOS
cin>>n>>m>>q;
vector<int> xi(m+1);
rep(i,1,m) cin>>xi[i],s.insert(xi[i]);
rep(i,1,m){
int a;cin>>a;
v[xi[i]]=a;
}
t.build(1,1,n);
int last=-1;
set<int>::iterator it;
for(auto vi:s){
if(last!=-1){
t.mod1(1,1,n,last+1,vi,1ll*vi*v[last]);
t.mod2(1,1,n,last+1,vi,v[last]);
}
last=vi;
}
//rep(i,1,n) t.ask(1,1,n,i,i);
rep(i,1,q){
int op,x,k;
cin>>op>>x>>k;
if(op==2){
cout<<t.ask(1,1,n,x,k)<<endl;
}
else{
it=s.lower_bound(x);
int r=*it;it--;int l=*it;
s.insert(x);v[x]=k;
t.mod1(1,1,n,l+1,x,1ll*x*v[l]);
t.mod2(1,1,n,l+1,x,v[l]);
t.mod1(1,1,n,x+1,r,1ll*r*k);
t.mod2(1,1,n,x+1,r,k);
}
}
return 0;
}
/*
8 3 4
1 3 8
3 24 10
2 2 5
1 5 15
2 5 5
2 7 8
*/