I Hate It
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 93269 Accepted Submission(s): 35359
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。
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
PS:通过ios::sync_with_stdio(false);可以加快数据cin、cout的输入输出
分析:
如果直接在每一步进行遍历求最大值，时间复杂度为O(n*m),所以考虑数据结构中的线段树
算法模板 (线段树)（1、build_tree(int i, int l, int r)；2、update_tree(int r)；3、query_tree(int i, int l, intr)）:
void build_tree(int i, int l, int r)
{
node[i].l = l;
node[i].r = r;
node[i].value = ;
if (l == r)
{
pre[l] = i;
return ;
}
build_tree (i <<, l, (int)(floor(l+r)/2.0));
build_tree ((i <<) + , (int)(floor(l+r)/2.0)+, r);
} void update_tree(int r)
{
if (r == ) return ;
int f = r / ;
int a = node[f>>].value;
int b = node[(f>>)+].value;
node[f].value = max(a, b);
update_tree(f);
} void query_tree(int i, int l, int r)
{
if (node[i].l == l && ndoe[i].r == r)
{
ans = max(ans, node[i].value);
return ;
}
i = i<<;
if (l <= node[i].r)
{
if (r <= node[i].r) query_tree(i, l, r);
else query_tree(i, l, node[i].r);
}
++ i;
if (r >= node[i].l)
{
if (l >= node[i].l) query_tree(i, l, r);
else query_tree(i, node[i].l, r);
}
}
C/C++代码实现（AC）：
#include <bits/stdc++.h> using namespace std; const int MAXNODE = <<;
const int MAXN = 2e6 + ;
int pre[MAXN], n, m, temp, ans; struct node
{
int l, r, value;
}P[MAXNODE]; void build_tree(int i, int l, int r)
{
P[i].l = l;
P[i].r = r;
P[i].value = ;
if (l == r)
{
pre[l] = i;
return ;
}
build_tree(i<<, l, (int)(floor(l + r) / 2.0));
build_tree((i<<) + , (int)(floor(l + r) / 2.0) + , r);
} void update_tree(int r)
{
if (r == ) return ;
int f = r / ;
int a = P[f<<].value;
int b = P[(f<<)+].value;
P[f].value = max(a, b);
update_tree(f);
} void query_tree(int i, int l, int r)
{
if (P[i].l == l && P[i].r == r)
{
ans = max(ans, P[i].value);
return ;
}
i = i <<;
if (l <= P[i].r)
{
if (r <= P[i].r) query_tree(i, l, r);
else query_tree(i, l, P[i].r);
}
i ++;
if (r >= P[i].l)
{
if (l >= P[i].l) query_tree(i, l, r);
else query_tree(i, P[i].l, r);
}
} int main()
{
ios::sync_with_stdio(false);
while(cin >>n >>m)
{
build_tree(, , n);
for(int i = ; i <= n; ++i)
{
cin >>temp;
P[pre[i]].value = temp;
update_tree(pre[i]);
}
int a, b;
char op;
while(m --)
{
ans = ;
cin >>op >>a >>b;
if (op == 'Q')
{
query_tree(, a, b);
cout <<ans <<endl;
}
else
{
P[pre[a]].value = b;
update_tree(pre[a]);
}
}
}
return ;
}