本文共 1763 字,大约阅读时间需要 5 分钟。
给定n个数,你的任务是实现下面的两种操作,S x y把第x个数改成y(y是小于10的9次方的非负整数),M x y计算第x个数到第y个数的和
多组数据,第一行为整数n(1<=n<=200000),接下来n个整数(每个整数都是小于10的9次方的非负整数),接下来有不超过200000的操作,以END结束
对于每一个M操作,输出x到y的和
31 2 3M 1 3S 2 6M 1 3END
6 10 #include#include #include #include #include using namespace std;const int inf=0x3f3f3f3f;const int maxn=200010;long long num[maxn<<2],a[maxn],fans[maxn];void buildtree(int le,int ri,int node){ if(le==ri){ num[node]=a[le]; return ; } int t=(le+ri)>>1; buildtree(le,t,node<<1); buildtree(t+1,ri,node<<1|1); num[node]=num[node<<1]+num[node<<1|1];}void update(int pos,long long val,int le,int ri,int node){ if(le==ri){ num[node]=val; return ; } int t=(le+ri)>>1; if(pos<=t) update(pos,val,le,t,node<<1); else update(pos,val,t+1,ri,node<<1|1); num[node]=num[node<<1]+num[node<<1|1];}long long query(int l,int r,int le,int ri,int node){ if(l<=le&&ri<=r) return num[node]; int t=(le+ri)>>1; long long ans=0; if(l<=t) ans+=query(l,r,le,t,node<<1); if(r>t) ans+=query(l,r,t+1,ri,node<<1|1); return ans;}int main(){ int n,pos,u,v; long long val; char ch[10]; while(scanf("%d",&n)!=-1){ for(int i=1;i<=n;i++) scanf("%lld",&a[i]); buildtree(1,n,1); int k=0; while(scanf("%s",ch)){ if(ch[0]=='E') break; if(ch[0]=='S'){ scanf("%d%lld",&pos,&val); update(pos,val,1,n,1); }else{ scanf("%d%d",&u,&v); fans[k++]=query(u,v,1,n,1); } } for(int i=0;i
转载地址:http://dsali.baihongyu.com/