题目链接
Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。
这让很多学生很反感。
不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。
这让很多学生很反感。
不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试,请处理到文件结束。
在每个测试的第一行,有两个正整数 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。
在每个测试的第一行,有两个正整数 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。
Output
对于每一次询问操作,在一行里面输出最高成绩。
Sample Input
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
Sample Output
5
6
5
9
Hint
Huge input,the C function scanf() will work better than cin题解:
裸的线段树。
#include <stdio.h> #include <algorithm> #include <cmath> #include <cstring> #include <deque> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <utility> #include <vector> #define mem(arr, num) memset(arr, 0, sizeof(arr)) #define _for(i, a, b) for (int i = a; i <= b; i++) #define __for(i, a, b) for (int i = a; i >= b; i--) #define IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; typedef long long ll; const ll inf = 0x3f3f3f3f; const double EPS = 1e-10; const ll mod = 1000000007LL; const int N = 1 << 19; ll dat[N]; int n; void init(int n_) { n = 1; while(n < n_) n *= 2; _for(i, 1, n * 2 -1) dat[i] = 0; } void update(int k, int a) { k += n-1; dat[k] = a; while(k > 1) { k >>= 1; dat[k] = max(dat[k*2], dat[k*2 + 1]); } } int query(int a, int b, int k, int l, int r) { if(a > r || b < l) return -1; if(a <=l && b >= r) return dat[k]; else { int vl = query(a, b, k * 2, l, (l + r)/2); int vr = query(a, b, k * 2 + 1,(l+r)/2 + 1,r); return max(vl, vr); } } int main(){ IO int nn, mm, x, y; char str; while(cin >> nn >> mm) { init(nn); _for(i, 1, nn) { cin >> x; update(i,x); } _for(i, 1, mm) { cin >> str >> x >> y; if(str == 'Q') cout << query(x,y,1,1,n) << endl; if(str == 'U') update(x,y); } } return 0; }