首页 > 代码库 > 1082 线段树练习 3
1082 线段树练习 3
1082 线段树练习 3
时间限制: 3 s
空间限制: 128000 KB
题目等级 : 大师 Master
题目描述 Description
给你N个数，有两种操作：
1：给区间[a,b]的所有数增加X
2：询问区间[a,b]的数的和。
输入描述 Input Description
第一行一个正整数n，接下来n行n个整数，
再接下来一个正整数Q，每行表示操作的个数，
如果第一个数是1，后接3个正整数，
表示在区间[a,b]内每个数增加X,如果是2，
表示操作2询问区间[a,b]的和是多少。
pascal选手请不要使用readln读入
输出描述 Output Description
对于每个询问输出一行一个答案
样例输入 Sample Input
3
1
2
3
2
1 2 3 2
2 2 3
样例输出 Sample Output
9
数据范围及提示 Data Size & Hint
数据范围
1<=n<=200000
1<=q<=200000
线段树：区间增减 和 区间查询。
1 #include<cstdio> 2 #define lson l,m,rt << 1 3 #define rson m+1,r,rt<<1|1 4 #define ll long long 5 6 const int N = 200010; 7 8 ll sum[N<<2]; 9 ll add[N<<2];10 int n,q;11 12 void pushup(int rt)13 {14 sum[rt] = sum[rt<<1] + sum[rt<<1|1];15 }16 void pushdown(int rt,int m) //m长度，rt线段 17 {18 if(add[rt])19 {20 add[rt<<1] += add[rt] ;21 add[rt<<1|1] += add[rt];22 sum[rt<<1] += add[rt] * (m - (m>>1));23 sum[rt<<1|1] += add[rt] * (m>>1);24 add[rt] = 0;25 }26 }27 void build(int l,int r,int rt)28 {29 add[rt] = 0;30 if(l==r)31 {32 scanf("%d",&sum[rt]);33 return ;34 }35 int m = (l+r)>>1;36 build(lson);37 build(rson);38 pushup(rt); 39 }40 void update(int L,int R,int c,int l,int r,int rt)41 {42 if(L<=l && r<=R)43 {44 add[rt] += c;45 sum[rt] += (ll)c * (r-l+1);46 return ;47 }48 pushdown(rt,r-l+1);49 int m = (l+r)>>1;50 if(L<=m) update(L,R,c,lson);51 if(m<R) update(L,R,c,rson);52 pushup(rt);53 }54 ll query(int L,int R,int l,int r,int rt)55 {56 if(L<=l && r<=R)57 {58 return sum[rt];59 }60 pushdown(rt,r-l+1);61 ll ret=0;62 int m = (l+r)>>1;63 if(L<=m) ret += query(L,R,lson);64 if(m<R) ret += query(L,R,rson);65 return ret;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,c,x;75 scanf("%d",&x);76 if(x==1)77 {78 scanf("%d%d%d",&a,&b,&c);79 update(a,b,c,1,n,1);80 }81 else82 {83 scanf("%d%d",&a,&b);84 printf("%lld\n",query(a,b,1,n,1));85 }86 }87 return 0;88 }
1082 线段树练习 3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。