士兵杀敌（二）
时间限制： 1000 ms | 内存限制： 65535 KB
难度： 5
- 描写叙述
-
南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。
小工是南将军手下的军师，南将军常常想知道第m号到第n号士兵的总杀敌数。请你帮助小工来回答南将军吧。
南将军的某次询问之后士兵i可能又杀敌q人，之后南将军再询问的时候。须要考虑到新增的杀敌数。
- 输入
- 仅仅有一组測试数据 第一行是两个整数N,M，当中N表示士兵的个数(1<N<1000000)，M表示指令的条数。
(1<M<100000)
随后的一行是N个整数，ai表示第i号士兵杀敌数目。(0<=ai<=100) 随后的M行每行是一条指令，这条指令包括了一个字符串和两个整数，首先是一个字符串，假设是字符串QUERY则表示南将军进行了查询操作，后面的两个整数m,n，表示查询的起始与终止士兵编号；假设是字符串ADD则后面跟的两个整数I,A(1<=I<=N,1<=A<=100),表示第I个士兵新增杀敌数为A. 输出 - 对于每次查询，输出一个整数R表示第m号士兵到第n号士兵的总杀敌数。每组输出占一行 例子输入
-
5 61 2 3 4 5QUERY 1 3ADD 1 2QUERY 1 3ADD 2 3QUERY 1 2QUERY 1 5
例子输出 -
688
-
#include
#include #include #include using namespace std;#define maxn 1000001#define inf 0x3f3f3f3fint ll[maxn<<2],rr[maxn<<2],sum[maxn<<2];int a[maxn];void build(int l,int r,int i){ ll[i]=l; rr[i]=r; if(ll[i]==rr[i]){ sum[i]=a[l]; return ; } int m=(l+r)>>1,ls=i<<1,rs=ls|1; build(l,m,ls); build(m+1,r,rs); sum[i]=sum[ls]+sum[rs];}void update(int k,int v,int i){ if(ll[i]==rr[i]){ sum[i]+=v; return; } int m=(ll[i]+rr[i])>>1,ls=i<<1,rs=ls|1; if(k<=m){ update(k,v,ls); } else{ update(k,v,rs); } sum[i]=sum[ls]+sum[rs];}int finds(int l,int r,int i){ if(ll[i]==l&&rr[i]==r){ return sum[i]; } int m=(ll[i]+rr[i])>>1,ls=i<<1,rs=ls|1; if(r<=m){ return finds(l,r,ls); } else if(l>m){ return finds(l,r,rs); } else{ return finds(l,m,ls)+finds(m+1,r,rs); }}int main(){ int n,m; int x,y; int A,I; char q[10]; freopen("in.txt","r",stdin); while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } build(1,n,1); for(int i=1;i<=m;i++){ scanf("%s",q); if(!strcmp(q,"QUERY")){ scanf("%d%d",&x,&y); printf("%d\n",finds(x,y,1)); } else { scanf("%d%d",&A,&I); update(A,I,1); } } }}
- 仅仅有一组測试数据 第一行是两个整数N,M，当中N表示士兵的个数(1<N<1000000)，M表示指令的条数。
版权声明：本文博客原创文章，博客，未经同意，不得转载。