T3树状数组,求条
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,q;
int ans;
int f[100010],g[100010];
int pre[100010];
int sum[100010];
int tree[200010][2];
int lowbit(int x){
return x&(-x);
}
void add1(int x,int k){
while(x<=n){
tree[x][0]+=k;
tree[x][0]%=mod;
x+=lowbit(x);
}
}
int sum1(int x){
int num=0;
while(x){
num+=tree[x][0];
num%=mod;
x-=lowbit(x);
}
return num;
}
void add2(int x,int k){
while(x<=n){
tree[x][1]+=k;
tree[x][1]%=mod;
x+=lowbit(x);
}
}
int sum2(int x){
int num=0;
while(x){
num+=tree[x][1];
num%=mod;
x-=lowbit(x);
}
return num;
}
signed main(){
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>f[i],add1(i,f[i]);
for(int i=1;i<=n;i++) cin>>g[i],add2(i,g[i]);
for(int i=1;i<=n;i++){
pre[i]=(pre[i-1]+g[i])%mod;
sum[i]=(sum[i-1]+f[i])%mod;
}
for(int i=1;i<=n;i++){
ans+=(f[i]*(((pre[n]-pre[i])*2+g[i]+2*mod)%mod))%mod;
ans%=mod;
}
while(q--){
int op,id,x;
cin>>op>>id>>x;
if(op==1){
ans+=(x-f[id]+mod)%mod*(((sum2(n)-sum2(id))*2+g[id]+mod)%mod)%mod;
add1(id,x-f[id]);
f[id]=x;
}
else{
ans+=(x-g[id]+mod)%mod*((2*sum1(id-1)+f[id])%mod)%mod;
g[id]=x;
add2(id,x-g[id]);
}
ans+=mod;ans%=mod;
cout<<ans<<'\n';
}
return 0;
}