「CODEVS1082」线段树练习 3
题目描述 Description
给你N个数，有两种操作：
1：给区间[a,b]的所有数增加X
2：询问区间[a,b]的数的和。
输入描述 Input Description
第一行一个正整数n，接下来n行n个整数，
再接下来一个正整数Q，每行表示操作的个数，
如果第一个数是1，后接3个正整数，
表示在区间[a,b]内每个数增加X,如果是2，
表示操作2询问区间[a,b]的和是多少。
输出描述 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include<iostream> #include<cstdio> using namespace std; int n,q,a[200001]; struct data{ int l,r; long long sum; int tag; }tr[800001]; void build(int k,int s,int t) { tr[k].l=s;tr[k].r=t; if(s==t){tr[k].sum=a[s];return;} int mid=(s+t)>>1; build(k<<1,s,mid); build(k<<1|1,mid+1,t); tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum; } void pushdown(int k) { int x=tr[k].r-tr[k].l+1; tr[k<<1].tag+=tr[k].tag; tr[k<<1|1].tag+=tr[k].tag; tr[k<<1].sum+=(x-(x>>1))*tr[k].tag; tr[k<<1|1].sum+=(x>>1)*tr[k].tag; tr[k].tag=0; } void update(int k,int a,int b,int x) { int l=tr[k].l,r=tr[k].r; if(a==l&&r==b) { tr[k].tag+=x; tr[k].sum+=(b-a+1)*x; return; } if(tr[k].tag)pushdown(k); int mid=(l+r)>>1; if(b<=mid)update(k<<1,a,b,x); else if(a>mid)update(k<<1|1,a,b,x); else { update(k<<1,a,mid,x); update(k<<1|1,mid+1,b,x); } tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum; } long long ask(int k,int a,int b) { int l=tr[k].l,r=tr[k].r; if(a==l&&b==r){return tr[k].sum;} if(tr[k].tag)pushdown(k); int mid=(l+r)>>1; if(b<=mid)return ask(k<<1,a,b); else if(a>mid)return ask(k<<1|1,a,b); else return (ask(k<<1,a,mid)+ask(k<<1|1,mid+1,b)); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); scanf("%d",&q); for(int i=1;i<=q;i++) { int t,a,b,x; scanf("%d",&t); if(t==1){ scanf("%d%d%d",&a,&b,&x); update(1,a,b,x); } else{ scanf("%d%d",&a,&b); printf("%lld\n",ask(1,a,b)); } } return 0; } |
Subscribe
计数器 9855329
OI 课件=>
OI 课件=>