Time Limit: 1000MS Memory Limit: 65536KB
SubmitStatistic
bLue有一個神器的機器，這個機器可以讀入一個數(shù)組，并按照用戶要求快速地進行數(shù)組的處理和計算，它支持如下兩種操作：
操作 1：把數(shù)組中第 p個元素的值增加 v。操作 2：計算數(shù)組中 [l, r]區(qū)間內(nèi)所有數(shù)的和。這個機器就是這么的神奇，但是 bLue的計算機壞掉了，你能幫他修一下嗎？
輸入數(shù)據(jù)有多組（數(shù)據(jù)組數(shù)不超過 20），到 EOF 結(jié)束。
對于每組數(shù)據(jù)：
第 1行輸入一個整數(shù) n (1 <= n <= 10^5)，表示數(shù)組中元素的個數(shù)。第 2行輸入 n 個用空格隔開的整數(shù) ai (1 <= ai <= 10^10)，表示初始輸入到計算機中的數(shù)組。第 3行輸入一個整數(shù) q (1 <= q <= 50000)，表示用戶的操作次數(shù)。接下來 q行，每行輸入先輸入 1 個整數(shù)，表示操作類型，根據(jù)不同的操作類型：如果類型為 1，則緊接著輸入 2個用空格隔開的整數(shù) p (1 <= p <= n) 和 v (1 <= v <= 10^10)，表示要把數(shù)組中第 p 個數(shù)的值增加 v。如果類型為 2，則緊接著輸入 2個用空格隔開的整數(shù) l, r (1 <= l <= r <= n)，表示要計算區(qū)間 [l, r]內(nèi)所有數(shù)的和（數(shù)組下標從 1 開始）。對于每組數(shù)據(jù)中的每次類型為 2的操作，輸出 1行，包含一個整數(shù)，表示計算出的和。
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****************************************************/
新聞熱點
疑難解答
