打卡信奥刷题（2539）用C++实现信奥 P2068 统计和

P2068 统计和

题目描述

给定一个长度为n(0≤n≤105)n(0\leq n\leq 10^5)n(0≤n≤105)，初始值都为000的序列，x(0≤x≤105)x(0\leq x\leq 10^5)x(0≤x≤105)次的修改某些位置上的数字，每次加上一个数，并在此期间提出y(0≤y≤105)y(0\leq y\leq 10^5)y(0≤y≤105)个问题，求每段区间的和。

输入格式

第一行111个整数，表示序列的长度nnn。

第二行111个整数，表示操作的次数w(0≤w≤2×105)w(0\leq w\leq 2\times 10^5)w(0≤w≤2×105)。

后面依次是www行，分别表示加入和询问操作。

其中，加入用x表示，询问用y表示。

xxx的格式为x a b表示在序列上第aaa个数加上bbb。保证1≤a≤n1 \leq a \leq n1≤a≤n，1≤b≤1091 \leq b \leq 10^91≤b≤109。

yyy的格式为y a b表示询问aaa到bbb区间的加和。保证1≤a≤b≤n1 \leq a \leq b \leq n1≤a≤b≤n。

输出格式

每行一个正整数，分别是每次询问的结果。

输入输出样例 #1

输入 #1

5 4 x 3 8 y 1 3 x 4 9 y 3 4

输出 #1

8 17

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5*4;intn,m;longlongtree[N*4];voidchange_point(intk,intl,intr,intx,intv)//单点修改{if(r<x||l>x)return;//当前区间与原序列的位置完全无交集if(l==x&&r==x)//当前结点为对应的叶子结点{tree[k]+=v;return;}intmid=(l+r)/2;change_point(k*2,l,mid,x,v);change_point(k*2+1,mid+1,r,x,v);//修改右子区间tree[k]=tree[k*2]+tree[k*2+1];//更新相关的值}longlongsearch(intk,intl,intr,intx,inty){if(y<l||x>r)return0;//当前区间与原序列的位置完全无交集,返回一个不影响答案的值if(l>=x&&r<=y)returntree[k];//询问区间在当前区间，返回维护好的值intmid=(l+r)/2;returnsearch(k*2,l,mid,x,y)+search(k*2+1,mid+1,r,x,y);}intmain(){scanf("%d %d",&n,&m);for(inti=1;i<=m;i++){charc;intx,y;cin>>c>>x>>y;if(c=='x')change_point(1,1,n,x,y);//单点修改if(c=='y')printf("%lld\n",search(1,1,n,x,y));//区间查询}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容