首页 > 代码库 > codevs 1082 线段树练习 3
codevs 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
这题需要开long long，函数也要开！坑
1 //s d s 2 #include<cstdio> 3 #include<iostream> 4 #include<cstdlib> 5 using namespace std; 6 const int N=5000006; 7 long long a[N],sum[N];int miku[N]; 8 long long b,c,d,e; 9 10 void update(int rt)11 {12 sum[rt]=sum[rt<<1]+sum[rt<<1|1];13 }14 15 void build(int l,int r,int rt)16 {17 if(l==r)18 {19 sum[rt]=a[l];20 return ;21 }22 int m=(l+r)>>1;23 build(l,m,rt<<1);24 build(m+1,r,rt<<1|1);25 update(rt);26 }27 28 void midify_interval(int l,int r,int rt,int nowl,int nowr,int neww)29 {30 if(nowl==l&&nowr==r)31 {32 miku[rt]+=neww;33 sum[rt]+=neww*(r-l+1);34 return ;35 }36 int m=(l+r)>>1;37 sum[rt<<1]+=miku[rt]*(m-l+1);38 sum[rt<<1|1]+=miku[rt]*(r-m);39 miku[rt<<1]+=miku[rt];40 miku[rt<<1|1]+=miku[rt];41 miku[rt]=0;42 if(nowr<=m) midify_interval(l,m,rt<<1,nowl,nowr,neww);43 else if(nowl>m) midify_interval(m+1,r,rt<<1|1,nowl,nowr,neww);44 else 45 {46 midify_interval(l,m,rt<<1,nowl,m,neww);47 midify_interval(m+1,r,rt<<1|1,m+1,nowr,neww);48 }49 update(rt);50 }51 52 long long query(int l,int r,int rt,int nowl,int nowr)53 {54 if(nowl<=l&&nowr>=r)55 {56 return sum[rt];57 }58 int m=(r+l)>>1;59 sum[rt<<1]+=miku[rt]*(m-l+1);60 sum[rt<<1|1]+=miku[rt]*(r-m);61 miku[rt<<1]+=miku[rt];62 miku[rt<<1|1]+=miku[rt];63 miku[rt]=0;64 long long ans=0;65 if(nowl<=m) ans+=query(l,m,rt<<1,nowl,nowr);66 if(nowr>m)ans+=query(m+1,r,rt<<1|1,nowl,nowr);67 return ans;68 }69 70 71 72 int main()73 {74 int n;75 scanf("%lld",&n);76 for(int i=1;i<=n;i++)scanf("%lld",a+i);77 build(1,n,1);78 int m;79 scanf("%lld",&m);80 81 for(int i=1;i<=m;i++)82 {83 scanf("%lld",&b);84 if(b==1)85 {86 scanf("%lld%lld%lld",&c,&d,&e);87 midify_interval(1,n,1,c,d,e);88 }89 if(b==2)90 {91 scanf("%lld%lld",&c,&d);92 printf("%lld\n",query(1,n,1,c,d));93 }94 }95 return 0;96 97 }
codevs 1082 线段树练习 3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。