首页 > 代码库 > 1081 线段树练习 2
1081 线段树练习 2
1081 线段树练习 2
codevs 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
线段树：区间增减 与 单点查询。
但是不知道为什么，有一组则是数据运行时输出结果正常，但评测时，却不正确。求解答
输入数据 (显示前20行) 5 2 3 1 4 5 2 1 1 1 1 2 1
你的答案 < 1
正确答案 > 3
本题来自codevs 1081
1 #include<iostream> 2 #include<cstdio> 3 #define lson l , m , rt << 1 4 #define rson m+1, r , rt << 1 | 1 5 #define LL long long 6 using namespace std; 7 8 const int N = 100010 ; 9 10 int add[N<<2];11 int sum[N<<2];12 int n,q;13 14 void pushup(int rt)15 {16 sum[rt] = sum[rt<<1] + sum[rt<<1|1] ;17 }18 void pushdown(int rt,int m) //rt线段,m长度 19 {20 if (add[rt])21 { 22 add[rt<<1] += add[rt]; 23 add[rt<<1|1] += add[rt]; 24 sum[rt<<1] += add[rt] * (m - (m >> 1)); 25 sum[rt<<1|1] += add[rt] * (m >> 1); 26 add[rt] = 0; 27 } 28 }29 void build(int l,int r,int rt) 30 { 31 add[rt] = 0; 32 if (l == r) 33 { 34 scanf("%lld",&sum[rt]); 35 return ; 36 } 37 int m = (l + r) >> 1; 38 build(lson); 39 build(rson); 40 pushup(rt); 41 }42 void update(int L,int R,int c,int l,int r,int rt) //[L,R]的区间加上c 43 { 44 if (L <= l && r <= R)45 {46 add[rt] += c;47 sum[rt] += (LL)c * (r - l + 1);48 return ;49 }50 pushdown(rt , r - l + 1);51 int m = (l + r) >> 1;52 if (L <= m) update(L , R , c , lson);53 if (m < R) update(L , R , c , rson);54 pushup(rt);55 } 56 LL query(int x,int l,int r,int rt)57 { 58 if (x==l && x==r)59 {60 return sum[rt]; 61 }62 pushdown(rt , r - l + 1); 63 int m = (l + r) >> 1; 64 if (x <= m) return query(x , lson); 65 if (m < x) return query(x , rson); 66 }67 int main()68 {69 scanf("%d",&n);70 build(1,n,1);71 scanf("%d",&q);72 while(q--)73 {74 int a,b,x,y;75 scanf("%d",&a);76 if(a==1)77 {78 scanf("%d%d%d",&x,&y,&b);79 update(x,y,b,1,n,1);80 }81 else82 {83 scanf("%d",&b);84 printf("%lld\n",query(b,1,n,1));85 }86 }87 return 0;88 }
1081 线段树练习 2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。