最大值

1. 最大值（max.cpp/in/out）

题目描述

在N（1<=N<=100000）个数A1…An 组成的序列上进行M(1<=M<=100000)次操作，操作有两种： (1)1 x

y：表示修改A[x]为y； (1)2 x y：询问x 到y 之间的最大值。

输入

第一行输入N(1<=N<=100000)，表示序列的长度，接下来N 行输入原始序列；接下来一行输入

M(1<=M<=100000)表示操作的次数，接下来M 行，每行为1 x y 或2 x y

输出

对于每个操作(2)输出对应的答案。

样例输入

2 1 4

1 3 5

2 2 4

样例输出

****考试的写的答案有种翻译的感觉。。。他咋说我就咋做的。

 1 #include<iostream>
 2 #include<fstream>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,M,line[100010][3],maxn=0,x[100010],ans[100010]={0};
 6 struct treenode
 7 {
 8     int b;int e;   //b表示树的左端点，e表示树的右端点 
 9     int mn;       //mn表示这个区间内的最大值 
10 }tree[400010];
11 void inittree(int l,int r,int p)  //此乃建树的过程 
12 {
13     int m;
14     tree[p].b=l;
15     tree[p].e=r;
16     if(l==r)tree[p].mn=x[l];
17     else
18     {
19         m=(l+r)>>1;
20         inittree(l,m,p+p);
21         inittree(m+1,r,p+p+1);
22         tree[p].mn=max(tree[p+p].mn,tree[p+p+1].mn);
23     }
24 }
25 void ins(int np,int nn,int p)
26 {
27     int m;
28     if(tree[p].b==tree[p].e)tree[p].mn=nn;   //如果这个区间只有他自己个 那么这个区间的最大值就是改后的这个数 
29     else
30     {
31         m=(tree[p].b+tree[p].e)>>1;
32         if(np<=m)ins(np,nn,p+p);  //通过判断大小来搜索他的左儿子或右儿子 
33         else ins(np,nn,p+p+1);
34         tree[p].mn=max(tree[p+p].mn,tree[p+p+1].mn);  //他的最大值就是他左儿子和右儿子的最大值 
35     }
36 }
37 int calc(int p,int st,int en)
38 {
39     int m;
40     if(tree[p].b==st&&tree[p].e==en)
41     return tree[p].mn;  //如果他的左端点等于x右端点等于y这就是要求的那个区间返回他的最大值即可 
42     if(tree[p].b==tree[p].e)
43     return tree[p].mn;  //如果这个区间只有自己那么输出他即可 
44     else
45     {
46         m=(tree[p].b+tree[p].e)>>1;  //通过二分的方法寻找想要求的区间段 
47         if(en<=m)return calc(p+p,st,en); 
48         if(st>m)return calc(p+p+1,st,en);
49         return max(calc(p+p,st,m),calc(p+p+1,m+1,en));  //返回的最大值就是他的左儿子和右儿子的最大值 
50     }
51 }
52 void addans(int answer)
53 {
54     ans[0]++;
55     ans[ans[0]]=answer;  //把答案存进数组里面 
56 }
57 int main()
58 {
59     int i,j;
60     cin>>n;
61     for(i=1;i<=n;i++)
62     scanf("%d",&x[i]);
63     inittree(1,n,1);  //建树 
64     cin>>M;
65     for(i=1;i<=M;i++)
66     {
67         int temp,tx,ty;
68         scanf("%d %d %d",&temp,&tx,&ty);
69         if(temp==1)
70         {
71             ins(tx,ty,1);  //更改 
72         }
73         if(temp==2)
74         addans(calc(1,tx,ty));  //calc求区间最大值 ，addans存答案 
75     }
76     for(i=1;i<=ans[0];i++)  //输出答案 
77     printf("%d
",ans[i]);
78     return 0;
79 }

****这道题要用线段树做，线段树里有一坨的二分。