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;

}

全部评论
学学 markdown 语法吧,你这样给谁看啊
点赞 回复 分享
发布于 2024-10-18 21:41 上海

相关推荐

程序员小白条:这比例牛逼,750:1
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务