题目：最高分是多少题意：查询区间内的最大值，修改单点的值题解：线段树——区间查询+单点修改陷阱：
输入多组样例：
while(EOF!=scanf(" %d %d", &N, &M))
查询时，不保证 a < b：
if(a>b){
swap(a, b);
}
原理：线段树详解代码：
#include
#include
#include
#include
using namespace std;
#define maxN 30000+3
#define maxM 5000+3
int segTree[maxN<<2];
int score[maxN];
void build(int node, int left, int right){
if(left==right){
segTree[node]=score[left];
return;
}
int mid=(left+right)>>1;
build(node<<1, left, mid);
build(node<<1|1, mid+1, right);
segTree[node]=max(segTree[node<<1], segTree[node<<1|1]);
}
int query(int node, int left, int right, int ql, int qr){
if(ql<=left && qr>=right){
return segTree[node];
}
int mid=(left+right)>>1;
int ansl=-1, ansr=-1;
if(ql<=mid){
ansl=query(node<<1, left, mid, ql, qr);
}
if(qr>mid){
ansr=query(node<<1|1, mid+1, right, ql, qr);
}
return max(ansl, ansr);
}
void update(int node, int left, int right, int ind, int value){
if(left==right && left==ind){
segTree[node]=value;
return;
}
int mid=(left+right)>>1;
if(ind<=mid){
update(node<<1, left, mid, ind, value);
}
else if(ind>mid){
update(node<<1|1, mid+1, right, ind, value);
}
segTree[node]=max(segTree[node<<1], segTree[node<<1|1]);
}
int main(){
int N, M;
while(EOF!=scanf(" %d %d", &N, &M)){
for(int i=1; i<=N; ++i){
scanf("%d", score+i);
}
memset(segTree, 0, sizeof(segTree));
build(1, 1, N);
char ch;
int a, b;
int ans;
while(M--){
scanf(" %c %d %d", &ch, &a, &b);
if('Q'==ch){
if(a>b){
swap(a, b);
}
ans=query(1, 1, N, a, b);
printf("%d\n", ans);
}
else if('U'==ch){
update(1, 1, N, a, b);
}
}
}
return 0;
}
/*
5 7
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 4 5
U 2 9
Q 1 5
*/
转载请注明原文地址: https://www.6miu.com/read-10692.html
