http://codevs.cn/problem/1081/
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 大师 Master
题目描述 Description
给你N个数，有两种操作
1：给区间[a,b]的所有数都增加X
2：询问第i个数是什么？
输入描述 Input Description
第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是1，后接3个正整数a,b,X，表示在区间[a,b]内每个数增加X,如果是2，后面跟1个整数i, 表示询问第i个位置的数是多少。
输出描述 Output Description
对于每个询问输出一行一个答案
样例输入 Sample Input
3
1
2
3
2
1 2 3 2
2 3
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
数据范围
1<=n<=100000
1<=q<=100000
分类标签 Tags 点此展开
1 #include <iostream> 2 #define maxn 100005 3 4 using namespace std; 5 6 int n,m,x,a,b,X; 7 struct node 8 { 9 int now,dis,l,r,mid,flag; 10 }tree[maxn*4]; 11 12 void tree_up(int now) 13 { 14 tree[now].dis=tree[now*2].dis+tree[now*2+1].dis; 15 return ; 16 } 17 18 void tree_build(int now,int l,int r) 19 { 20 tree[now].l=l,tree[now].r=r; 21 if(tree[now].l==tree[now].r) 22 { 23 cin>>tree[now].dis; 24 return ; 25 } 26 tree[now].mid=(tree[now].l+tree[now].r)/2; 27 tree_build(now*2,l,tree[now].mid); 28 tree_build(now*2+1,tree[now].mid+1,r); 29 tree_up(now); 30 } 31 32 void tree_down(int now) 33 { 34 tree[now*2].flag+=tree[now].flag; 35 tree[now*2].dis+=tree[now].flag*(tree[now*2].r-tree[now*2].l+1); 36 tree[now*2+1].flag+=tree[now].flag; 37 tree[now*2+1].dis+=tree[now].flag*(tree[now*2+1].r-tree[now*2+1].l+1); 38 tree[now].flag=0; return ; 39 } 40 41 void tree_change(int now,int l,int r,int x) 42 { 43 if(tree[now].l==l&&tree[now].r==r) 44 { 45 tree[now].dis+=x*(r-l+1); 46 tree[now].flag+=x; 47 return ; 48 } 49 if(tree[now].flag) tree_down(now); 50 if(tree[now].mid>=r) tree_change(now*2,l,r,x); 51 else if(tree[now].mid<l) tree_change(now*2+1,l,r,x); 52 else 53 { 54 tree_change(now*2,l,tree[now].mid,x); 55 tree_change(now*2+1,tree[now].mid+1,r,x); 56 } 57 tree_up(now); 58 } 59 60 int tree_query(int now,int to) 61 { 62 if(tree[now].l==tree[now].r) return tree[now].dis; 63 if(tree[now].flag) tree_down(now); 64 if(tree[now].mid>=to) return tree_query(now*2,to); 65 else if(tree[now].mid<to) return tree_query(now*2+1,to); 66 } 67 68 int main() 69 { 70 cin>>n; 71 tree_build(1,1,n); 72 cin>>m; 73 while(m--) 74 { 75 cin>>x; 76 if(x==1) 77 { 78 cin>>a>>b>>X; 79 tree_change(1,a,b,X); 80 } 81 else 82 { 83 cin>>X; 84 cout<<tree_query(1,X)<<endl; 85 } 86 } 87 return 0; 88 }