Range Add Query
数列 A = {a1,a2,...,an} に対し、次の２つの操作を行うプログラムを作成せよ。
- add(s,t,x): as,as+1,...,at にxを加算する。
- get(i): aiの値を出力する。
ただし、ai (i=1,2,...,n)は、0 で初期化されているものとする。
入力
n q query1 query2 : queryq
１行目にAの要素数n, クエリの数qが与えられる。続くq行に i 番目のクエリ queryi が与えられる。queryi は以下のいずれかの形式で与えられる。
0 s t x
または
1 i
各クエリの最初の数字は、クエリの種類を示し、'0'がadd(s,t,x)、'1'がget(i)を表す。
出力
各getクエリについて、値を１行に出力せよ。
制約
- 1≤n≤100000
- 1≤q≤100000
- 1≤s≤t≤n
- 1≤i≤n
- 0≤x≤1000
入力例 1
3 5 0 1 2 1 0 2 3 2 0 3 3 3 1 2 1 3
出力例 1
3 5
入力例 2
4 3 1 2 0 1 4 1 1 2
出力例 2
0 1
区间加 单点查
树状数组+差分 或 线段树
缩常数，继续打榜
1 #include <cstdio> 2 #include <cstdlib> 3 4 #define siz 10000000 5 6 char buf[siz], *bit = buf; 7 8 inline int nextInt(void) { 9 register int ret = 0; 10 register int neg = false; 11 12 for (; *bit < '0'; ++bit) 13 if (*bit == '-')neg ^= true; 14 15 for (; *bit >= '0'; ++bit) 16 ret = ret * 10 + *bit - '0'; 17 18 return neg ? -ret : ret; 19 } 20 21 int n, m; 22 23 int pre[100005]; 24 25 inline int ask(int p) { 26 int ret = 0; 27 for (; p; p -= p&-p) 28 ret += pre[p]; 29 return ret; 30 } 31 32 inline void add(int p, int k) { 33 for (; p <= n; p += p&-p) 34 pre[p] += k; 35 } 36 37 signed main(void) { 38 fread(buf, 1, siz, stdin); 39 40 n = nextInt(); 41 m = nextInt(); 42 43 for (int i = 1; i <= m; ++i) { 44 int c = nextInt(); 45 if (c) // get(i) 46 printf("%d ", ask(nextInt())); 47 else // add(s, t, x) 48 { 49 int x = nextInt(); 50 int y = nextInt(); 51 int k = nextInt(); 52 add(x, k); add(y + 1, -k); 53 } 54 } 55 56 //system("pause"); 57 }
@Author: YouSiki