传送门：HUD - 1754
题目描述
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
输入描述
本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取’Q’或’U’) ，和两个正整数A，B。
当C为’Q’的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为’U’的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
输出描述
对于每一次询问操作，在一行里面输出最高成绩。
思路分析
线段树维护区间最大值，单点更新
样例输入
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
样例输出
5
6
5
9
线段树代码
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define rson ro<<1|1,mid+1,r
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int INF = 0x3f3f3f3f;
const int N=1e6+10;
struct T{
int l,r,ma;
}tree[N<<2];
void pushup(int ro){
tree[ro].ma=max(tree[ls].ma,tree[rs].ma);
}
void build(int ro,int l,int r){
tree[ro].l=l,tree[ro].r=r,tree[ro].ma=-1;
if(l==r){
scanf("%d",&tree[ro].ma);
return ;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
pushup(ro);
}
void update(int ro,int x,int d){
if(tree[ro].l==x && tree[ro].r==x){
tree[ro].ma=d;
return ;
}
int mid=(tree[ro].l+tree[ro].r)>>1;
if(x<=mid)
update(ls,x,d);
else
update(rs,x,d);
pushup(ro);
}
int query(int ro,int l,int r){
if(l<=tree[ro].l && tree[ro].r<=r){
return tree[ro].ma;
}
int ans=-INF;
int mid=(tree[ro].l+tree[ro].r)>>1;
if(l<=mid)
ans=max(ans,query(ls,l,r));
if(r>mid)
ans=max(ans,query(rs,l,r));
return ans;
}
int main() {
int n,m;
while(~scanf("%d %d",&n,&m)){
build(1,1,n);
while(m--){
char op;
int l,r;
getchar();
scanf("%c%d%d",&op,&l,&r);
if(op=='U')
update(1,l,r);
else
printf("%d\n",query(1,l,r));
}
}
return 0;
}
分块代码
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define fi first
#define se second
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define umap unordered_map
#define uset unordered_set
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
const int INF = 0x3f3f3f3f;
const int N=2e5+10;
int blo,bel[N],num,l[N],r[N],Max[N];
int n,q,a[N];
void build() {
blo=sqrt(n);
num=n/blo;
if(n%blo)
num++;
for(int i=1; i<=num; i++) {
l[i]=(i-1)*blo+1;
r[i]=i*blo;
}
r[num]=n;
for(int i=1; i<=n; i++)
bel[i]=(i-1)/blo+1;
for(int i=1; i<=num; i++)
for(int j=l[i]; j<=r[i]; j++)
Max[i]=max(Max[i],a[j]);
}
void update(int x,int v) {
a[x]=v;
Max[bel[x]]=max(Max[bel[x]],a[x]);
}
int query(int x,int y) {
int ans=0;
if(bel[x]==bel[y]) {
for(int i=x; i<=y; i++)
ans=max(ans,a[i]);
return ans;
}
for(int i=x; i<=r[bel[x]]; i++)
ans=max(ans,a[i]);
for(int i=bel[x]+1; i<bel[y]; i++)
ans=max(ans,Max[i]);
for(int i=l[bel[y]]; i<=y; i++)
ans=max(ans,a[i]);
return ans;
}
int main() {
IOS;
#ifdef xiaofan
freopen("in.txt","r",stdin);
#endif
while(cin>>n>>q) {
mem(Max,0);
for(int i=1; i<=n; i++)
cin>>a[i];
build();
while(q--) {
char op;
int x,y;
cin>>op>>x>>y;
if(op=='Q')
cout<<query(x,y)<<endl;
else
update(x,y);
}
}
#ifdef xiaofan
cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
#endif
return 0;
}
