网站网站制作需要多少钱,有哪些网站是可以做宣传的,中装建设集团有限公司,企业网站ui问题 D: 【模板】线段树1 时间限制: 1 Sec 内存限制: 512 MB提交: 80 解决: 40[提交][状态][讨论版]题目描述 给定一个无序数列#xff0c;有四种操作#xff1a; 1.令数列中的某个数加上某个数 2.求一个区间的和 3.查询一段区间内的最大值#xff1b; 4.查询一段区间内的… 问题 D: 【模板】线段树1 时间限制: 1 Sec 内存限制: 512 MB提交: 80 解决: 40[提交][状态][讨论版] 题目描述 给定一个无序数列有四种操作 1.令数列中的某个数加上某个数 2.求一个区间的和 3.查询一段区间内的最大值 4.查询一段区间内的最小值 输入 输入的第1行共有两个数n和q表示数列长度和操作次数 输入的第2行共有n个数表示该数列 接下来共有q行每行有三个数 第1个数为操作类型具体如下 若是第1种操作接下来两个数xy分别表示将第x个数加y 若是第24种操作接下来两个数xy表示闭区间的左右端点 输出 输出共有若干行对于每一个询问输出一个整数结果 样例输入 5 4
1 2 3 4 5
2 1 4
1 3 -2
3 1 5
4 2 3 样例输出 10
5
1 提示 1n,q200000 保证所有数据在c/c语言的INT范围内pascal语言的longint范围内。 题解线段树模板题这个模板可支持区间加减。 代码如下 1 #includecstdio2 #includeiostream3 #define Max 2000004 using namespace std;5 int n,q;6 struct node{7 int maxn,minn,sum,mark;8 }tree[Max*3];9 void pushdown(int k,int l,int r){
10 tree[2*k].marktree[k].mark;
11 tree[2*k1].marktree[k].mark;
12 int lenr-l1;
13 tree[2*k].sumtree[k].mark*(len-len/2);
14 tree[2*k1].sumtree[k].mark*(len/2);
15 tree[k].mark0;
16 }
17 void update(int l,int r,int a,int b,int k,int add){
18 if(albr){
19 tree[k].maxnadd; tree[k].minnadd;
20 tree[k].sum(r-l1)*add; return;
21 }
22 if(l!rtree[k].mark) pushdown(k,l,r);
23 int mid(lr)/2;
24 if(amid) update(l,mid,a,b,2*k,add);
25 if(bmid) update(mid1,r,a,b,2*k1,add);
26 tree[k].maxnmax(tree[2*k].maxn,tree[2*k1].maxn);
27 tree[k].minnmin(tree[2*k].minn,tree[2*k1].minn);
28 tree[k].sumtree[2*k].sumtree[2*k1].sum;
29 }
30 int query(int l,int r,int a,int b,int k,int num){
31 if(albr){
32 if(num3) return tree[k].maxn;
33 if(num4) return tree[k].minn;
34 if(num2) return tree[k].sum;
35 }
36 if(l!rtree[k].mark) pushdown(k,l,r);
37 int mid(lr)/2;
38 if(bmid) return query(l,mid,a,b,2*k,num);
39 else if(amid) return query(mid1,r,a,b,2*k1,num);
40 else{
41 if(num3) return max(query(l,mid,a,mid,2*k,num),query(mid1,r,mid1,b,2*k1,num));
42 if(num4) return min(query(l,mid,a,mid,2*k,num),query(mid1,r,mid1,b,2*k1,num));
43 if(num2) return query(l,mid,a,mid,2*k,num)query(mid1,r,mid1,b,2*k1,num);
44 }
45 }
46 int main()
47 {
48 scanf(%d%d,n,q);
49 for(int i1;in;i){
50 int a; scanf(%d,a); update(1,n,i,i,1,a);
51 }
52 for(int i1;iq;i){
53 int num,x,y; scanf(%d%d%d,num,x,y);
54 if(num1) update(1,n,x,x,1,y);
55 if(num2) printf(%d\n,query(1,n,x,y,1,2));
56 if(num3) printf(%d\n,query(1,n,x,y,1,3));
57 if(num4) printf(%d\n,query(1,n,x,y,1,4));
58 }
59 return 0;
60 } 转载于:https://www.cnblogs.com/Beginner-/p/7467737.html
