sdutacm-数组计算机

2019-11-06 06:21:00

字体：大中小

来源：转载

供稿：网友

数组计算机

Time Limit: 1000MS Memory Limit: 65536KB

SubmitStatistic

PRoblemDescription

bLue有一个神器的机器，这个机器可以读入一个数组，并按照用户要求快速地进行数组的处理和计算，它支持如下两种操作：

操作 1：把数组中第 p个元素的值增加 v。操作 2：计算数组中 [l, r]区间内所有数的和。

这个机器就是这么的神奇，但是 bLue的计算机坏掉了，你能帮他修一下吗？

Input

输入数据有多组（数据组数不超过 20），到 EOF 结束。

对于每组数据：

第 1行输入一个整数 n (1 <= n <= 10^5)，表示数组中元素的个数。第 2行输入 n 个用空格隔开的整数 ai (1 <= ai <= 10^10)，表示初始输入到计算机中的数组。第 3行输入一个整数 q (1 <= q <= 50000)，表示用户的操作次数。接下来 q行，每行输入先输入 1 个整数，表示操作类型，根据不同的操作类型：如果类型为 1，则紧接着输入 2个用空格隔开的整数 p (1 <= p <= n) 和 v (1 <= v <= 10^10)，表示要把数组中第 p 个数的值增加 v。如果类型为 2，则紧接着输入 2个用空格隔开的整数 l, r (1 <= l <= r <= n)，表示要计算区间 [l, r]内所有数的和（数组下标从 1 开始）。

Output

对于每组数据中的每次类型为 2的操作，输出 1行，包含一个整数，表示计算出的和。

ExampleInput

51 2 3 4 552 1 22 1 51 4 102 4 52 1 5ExampleOutput
3151925Hint
Author
「2017年寒假集训分组测试赛2」bLue
#include <iostream>#include<stdio.h>#include<string.h>#include<algorithm>#include<stdlib.h>#include<bits/stdc++.h>using namespace std;#define M 100001#define lson l,m,bh*2#define rson m+1,r,bh*2+1long long sum[M*4];void pushup(int bh){   sum[bh] = sum[bh*2]+sum[bh*2+1];}void build(int l,int r, int bh){    if(l==r)    {        scanf("%lld",&sum[bh]);        return ;    }    int m = (l+r) / 2;    build(lson);    build(rson);    pushup(bh);}/*void build (int l,int r,int bh){    if(l==r)    {        scanf("%lld",&sum[bh]);        return ;    }    int  m = (l+r) / 2;    build(lson);    build(rson);    push(bh);}*/void update(int p,long long v,int l,int r,int bh){    if(l==r)    {        sum[bh]+=v;        return ;    }    int m = (l+r)/2;    if(p<=m) update(p,v,lson);    else update(p,v,rson);    pushup(bh);}long long ask(int L,int R,int l,int r,int bh){    if(L<=l&&r<=R) return sum[bh];    int m = (l+r)/2;    long long temp  = 0;    if(L<=m) temp +=ask(L,R,lson);    if(R>m) temp += ask(L,R,rson);    return temp;}int main(){  int n,p,l,r,o,op;  long long int v;  while(~scanf("%d",&n))  {    build(1,n,1);    scanf("%d",&o);    for(int i=0;i<o;i++)    {        scanf("%d",&op);        if(op==1)        {            scanf("%d %lld",&p,&v);            update(p,v,1,n,1);        }        if(op==2)        {            scanf("%d %d",&l,&r);            printf("%lld/n",ask(l,r,1,n,1));        }    }  }  return 0;}/***************************************************User name: jk160505徐红博Result: AcceptedTake time: 624msTake Memory: 904KBSubmit time: 2017-02-13 10:35:40****************************************************/