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 上海

相关推荐

Lorn的意义:1.你这根本就不会写简历呀,了解太少了 2.你这些项目经历感觉真的没啥亮点啊,描述的不行,重写书写一下让人看到核心,就继续海投 注意七八月份ofer还是比较多的,越往后机会越少,抓住时机,抓紧检查疏漏,加油查看图片
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-11 13:34
offe从四面八方来:我真的没时间陪你闹了
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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