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

线段树练习2

2024-09-20 18:33:48   217人阅读

1081 线段树练习 2

 

时间限制: 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

 1 #include<iostream>
 2 #include<cstdio>
 3 
 4 using namespace std;
 5 const int N=100001;
 6 
 7 int ans,n,m,z,x,y,yj;
 8 
 9 struct node{
10     int l,r,w,f;
11 }T[N*4];
12 
13 void down(int jd)
14 {
15     T[jd<<1].w+=T[jd].f*(T[jd<<1].r-T[jd<<1].l+1);
16     T[jd<<1|1].w+=T[jd].f*(T[jd<<1|1].r-T[jd<<1|1].l+1);
17     T[jd<<1].f+=T[jd].f;
18     T[jd<<1|1].f+=T[jd].f;
19     T[jd].f=0;
20 }
21 
22 void built(int l,int r,int jd)
23 {
24     T[jd].l=l;
25     T[jd].r=r;
26     if(T[jd].l==T[jd].r)
27     {
28         cin>>T[jd].w;
29         return ;
30     }
31     int mid=(l+r)>>1;
32     built(l,mid,jd<<1);
33     built(mid+1,r,jd<<1|1);
34     T[jd].w=T[jd<<1].w+T[jd<<1|1].w;
35 }
36 
37 void qj_gai(int jd)
38 {
39     if(x<=T[jd].l&&T[jd].r<=y)
40     {
41         T[jd].w+=(T[jd].r-T[jd].l+1)*yj;//xiang zheng jia shang le ji ge yj bian liang 
42         T[jd].f+=yj;
43         return ;
44     }
45     if(T[jd].f)down(jd);
46     int mid=(T[jd].l+T[jd].r)>>1;
47     if(x<=mid)qj_gai(jd<<1);
48     if(y>mid)qj_gai(jd<<1|1);
49     T[jd].w=T[jd<<1].w+T[jd<<1|1].w; 
50 }
51 
52 void po_ask(int jd)
53 {
54     if(T[jd].l==T[jd].r)
55     {
56         ans=T[jd].w;
57         return ;
58     }
59     if(T[jd].f)down(jd);
60     int mid=(T[jd].l+T[jd].r)>>1;
61     if(x<=mid)po_ask(jd<<1);
62     else po_ask(jd<<1|1);
63 }
64 
65 int main()
66 {
67     cin>>n;
68     built(1,n,1);    
69     cin>>m;
70     for(int i=1;i<=m;i++)
71     {
72         cin>>z;
73         if(z==1)
74         {
75             cin>>x>>y>>yj;
76             qj_gai(1);
77         }
78         if(z==2)
79         {
80             cin>>x;
81             po_ask(1);
82             cout<<ans<<endl;
83         }
84     }
85     return 0;
86 }

 

线段树练习2


联系
我们