首页 > 代码库 > 线段树练习3

线段树练习3

2024-09-20 19:10:50   217人阅读

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<iostream>
 2 #include<cstdio>
 3 #define ll long long
 4 
 5 using namespace std;
 6 const int N=200002;
 7 
 8 struct node{
 9     long long l,r,w,f;
10 }T[N*4];
11 
12 long long z,x,y,yj;
13 long long ans;
14 long long n,m;
15 
16 void down(ll jd)
17 {
18     T[jd<<1].w+=T[jd].f*(T[jd<<1].r-T[jd<<1].l+1);
19     T[jd<<1|1].w+=T[jd].f*(T[jd<<1|1].r-T[jd<<1|1].l+1);
20     T[jd<<1].f+=T[jd].f;
21     T[jd<<1|1].f+=T[jd].f;
22     T[jd].f=0;
23 }
24 
25 void build(ll l,ll r,ll jd)
26 {
27     T[jd].l=l;
28     T[jd].r=r;
29     if(T[jd].l==T[jd].r)
30     {
31         scanf("%lld",&T[jd].w);
32         return ;
33     }
34     int mid=(l+r)>>1;
35     build(l,mid,jd<<1);
36     build(mid+1,r,jd<<1|1);
37     T[jd].w=T[jd<<1].w+T[jd<<1|1].w;
38 }
39 
40 void qj_gai(ll jd)
41 {
42     if(x<=T[jd].l&&T[jd].r<=y)
43     {
44         T[jd].w+=(T[jd].r-T[jd].l+1)*yj;
45         T[jd].f+=yj;
46         return ;
47     }
48     if(T[jd].f)down(jd);
49     int mid=(T[jd].l+T[jd].r)>>1;
50     if(x<=mid)qj_gai(jd<<1);
51     if(y>mid)qj_gai(jd<<1|1);
52     T[jd].w=T[jd<<1].w+T[jd<<1|1].w;
53 }
54 
55 void qj_ask(ll jd)
56 {
57     if(x<=T[jd].l&&T[jd].r<=y)
58     {
59         ans+=T[jd].w;
60         return ;
61     }
62     if(T[jd].f)down(jd);
63     int mid=(T[jd].l+T[jd].r)>>1;
64     if(x<=mid)qj_ask(jd<<1);
65     if(y>mid)qj_ask(jd<<1|1);
66 }
67 
68 int main()
69 {
70     scanf("%lld",&n);
71     build(1,n,1);
72     scanf("%lld",&m);
73     for(int i=1;i<=m;i++)
74     {
75         scanf("%lld",&z);
76         if(z==1)
77         {
78             scanf("%lld%lld%lld",&x,&y,&yj);
79             qj_gai(1);
80         }
81         if(z==2)
82         {
83             scanf("%lld%lld",&x,&y);
84             ans=0;
85             qj_ask(1);
86             printf("%lld\n",ans);
87         }
88      }
89      return 0; 
90 }

ALL 开 long long

线段树练习3


联系
我们