wordpress全站源码,濮阳市城乡建设管理局网站,.net开发微信网站流程,网络规划设计师培训机构1081 线段树练习 2 时间限制: 1 s空间限制: 128000 KB题目等级 : 大师 Master题目描述 Description给你N个数#xff0c;有两种操作 1#xff1a;给区间[a,b]的所有数都增加X 2#xff1a;询问第i个数是什么#xff1f; 输入描述 Input Description第一行一个正整数n#… 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 数据范围 1n100000 1q100000 解题线段树的基本操作。。。 1 #include iostream2 #include cstdio3 #include cstring4 #include cmath5 #include algorithm6 #include climits7 #include vector8 #include queue9 #include cstdlib
10 #include string
11 #include set
12 #include stack
13 #define LL long long
14 #define pii pairint,int
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 const int maxn 100010;
18 struct node {
19 int lt,rt,val;
20 };
21 node tree[maxn2];
22 void build(int lt,int rt,int v) {
23 tree[v].lt lt;
24 tree[v].rt rt;
25 if(lt rt) {
26 scanf(%d,tree[v].val);
27 return;
28 }
29 tree[v].val 0;
30 int mid (lt rt)1;
31 build(lt,mid,v1);
32 build(mid1,rt,v1|1);
33 }
34 void update(int lt,int rt,int v,int val) {
35 if(tree[v].lt lt tree[v].rt rt) {
36 tree[v].val val;
37 return;
38 }
39 if(tree[v].val) {
40 tree[v1].val tree[v].val;
41 tree[v1|1].val tree[v].val;
42 tree[v].val 0;
43 return;
44 }
45 if(rt tree[v1|1].lt) update(lt,rt,v1|1,val);
46 if(lt tree[v1].lt) update(lt,rt,v1,val);
47 }
48 int query(int lt,int rt,int v) {
49 if(tree[v].lt lt tree[v].rt rt) {
50 return tree[v].val;
51 }
52 if(tree[v].val) {
53 tree[v1].val tree[v].val;
54 tree[v1|1].val tree[v].val;
55 tree[v].val 0;
56 }
57 if(lt tree[v1].rt) return query(lt,rt,v1);
58 if(rt tree[v1|1].lt) return query(lt,rt,v1|1);
59 }
60 int main() {
61 int n,m,op,a,b,x;
62 while(~scanf(%d,n)) {
63 build(1,n,1);
64 scanf(%d,m);
65 while(m--) {
66 scanf(%d,op);
67 if(op 1) {
68 scanf(%d %d %d,a,b,x);
69 update(a,b,1,x);
70 } else if(op 2) {
71 scanf(%d,a);
72 printf(%d\n,query(a,a,1));
73 }
74 }
75 }
76 return 0;
77 } View Code 转载于:https://www.cnblogs.com/crackpotisback/p/4066537.html
