HDU-1754 I Hate It

题目描述

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。 这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

输入

本题目包含多组测试，请处理到文件结束。 在每个测试的第一行，有两个正整数 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

提示

Huge input,the C function scanf() will work better than cin

思路

线段树，点更新操作，线段数维护区间最大值。

代码

//详细解释参见HDU-1166（内容基本一致。） #include <iostream> #include <math.h> #include <algorithm> #include <map> #include <queue> #include <string.h> #include <stdio.h> #include <fstream> #define mx 20000002 #define mem(a) memset(a,0,sizeof(a)) using namespace std; struct node { int l; int r; int m; }; node a[800020]; int num[200005]; void pushup (int i) { a[i].m = max(a[i<<1].m,a[i<<1|1].m); } void build (int l,int r,int i) { a[i].l=l; a[i].r=r; a[i].m=-1; if(l==r) { a[i].m=num[l]; return ; } int mid = (l+r)>>1; build(l,mid,i<<1); build(mid+1,r,i<<1|1); pushup(i); } void update (int x,int v,int i) { if(a[i].l == x&&a[i].r==x) { a[i].m=v; return ; } int mid = (a[i].l+a[i].r)>>1; if(x<=mid) update(x,v,i<<1); else update(x,v,i<<1|1); pushup(i); } int query (int l,int r,int i) { if(l<=a[i].l&&a[i].r<=r) return a[i].m; int mid = (a[i].l +a[i].r)>>1; if(r<=mid ) return query(l,r,i<<1); else if(l>mid) return query(l,r,i<<1|1); else return max(query(l,mid,i<<1),query(mid+1,r,i<<1|1)); } int main() { #ifndef ONLINE_JUDGE freopen("a","r",stdin); #endif // ONLINE_JUDGE ios_base::sync_with_stdio(false); cin.tie(0); mem(a); mem(num); char c; int n,t,x,y; while(cin>>n>>t) { for(int i=1; i<=n; ++i) cin>>num[i]; build(1,n,1); while(t--) { cin>>c>>x>>y; if(c=='Q') cout<<query(x,y,1)<<endl; else if(c=='U') update(x,y,1); } } return 0; }