I Hate It（线段树）

I Hate It

Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 28169    Accepted Submission(s): 11168

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

     题意：

     多case输入，每个case包含N（0到200000）个人和M（0到5000）条信息。随后给出N个人的成绩。信息有两类，当为Q  a  b时，表示求a到b号同学成绩最高的一位，输出这个成绩；当为C  a  b时，表示将a同学的成绩变为b成绩。

 

     思路：

     线段树基础题。求最大值。与之前做的求和条件有点不同而已，大致一样。将结构体的总和改成最大值就好了。

 

     AC：

#include<stdio.h>
#include<string.h>
#define MAX 2000000+5

typedef struct
{
	int st;  //区间起点
	int en;  //区间重点
	int max; //区间最大值
}node;

int student[MAX];
node no[MAX];
int ma;

//递归建树过程
void build(int from,int to,int i)
{
	int mid=(from+to)/2;
	no[i].st=from;
	no[i].en=to;
	if(from==to)
	{
		no[i].max=student[from];
		return;
	}
//当from==to的时候，只有自己的成绩，所以直接赋值就好了
	build(from,mid,2*i);
	build(mid+1,to,2*i+1);
	no[i].max=(no[2*i].max>no[2*i+1].max?no[2*i].max:no[2*i+1].max);
//这个条件改了，max值是对比最大得出
}

void change(int who,int grade,int i)
{
	int mid=(no[i].st+no[i].en)/2;
	if(no[i].st==no[i].en&&no[i].st==who)
	{
		no[i].max=grade;
		return;
	}
	if(who<=mid)   change(who,grade,2*i);
	if(who>=mid+1) change(who,grade,2*i+1);
	no[i].max=(no[2*i].max>no[2*i+1].max?no[2*i].max:no[2*i+1].max);
//同样的，这里也为对比赋值
}

void search(int from,int to,int i)
{
	int mid=(no[i].st+no[i].en)/2;
	if(from==no[i].st&&to==no[i].en)
	{
		ma=(ma>no[i].max?ma:no[i].max);
//这里也是对比得出
		return;
	}
	if(from>=mid+1) search(from,to,2*i+1);
	if(to<=mid)     search(from,to,2*i);
	if(from<=mid&&to>=mid+1)
	{
		search(from,mid,2*i);
		search(mid+1,to,2*i+1);
	}
}

int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(student,0,sizeof(student));
		memset(no,0,sizeof(no));
		for(int i=1;i<=n;i++)
			scanf("%d",&student[i]);
		build(1,n,1);
		while(m--)
		{
			char c;
			scanf(" %c",&c);
			if(c=='Q')
			{
				int from,to;
				scanf("%d%d",&from,&to);
				ma=0;
				search(from,to,1);
				printf("%d\n",ma);
			}
			if(c=='U')
			{
				int who,grade;
				scanf("%d%d",&who,&grade);
				change(who,grade,1);
			}
		}
	}
	return 0;
}

  

    14-07-19 更新 AC 代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>

using namespace std;

const int MAX = 200005;

int num[MAX], tree[MAX * 5];

void build (int node, int l, int r) {
        int mid = l + (r - l) / 2;

        if (l == r) {
                tree[node] = num[l];
        } else {
                build (node * 2, l, mid);
                build (node * 2 + 1, mid + 1, r);

                tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
        }
}

int query (int node, int l, int r, int al, int ar) {

        int mid = l + (r - l) / 2;

        if (ar < l || al > r) return -1;
        else if (al <= l && ar >= r) return tree[node];
        else return max( query(node * 2, l, mid, al, ar),
                         query(node * 2 + 1, mid + 1, r, al, ar) );

}

void update (int node, int l, int r, int num, int ans) {
        int mid = l + (r - l) / 2;

        if (l == r && l == num) tree[node] = ans;
        else {
                if (num <= mid) update(node * 2, l, mid, num, ans);
                else update(node * 2 + 1, mid + 1, r, num, ans);

                tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
        }

}

int main() {
        int n, m;

        while(~scanf("%d%d", &n, &m)) {

                for (int i = 1; i <= n; ++i) {
                        scanf("%d", &num[i]);
                }

                build(1, 1, n);

                while(m--) {
                        char q;
                        int a, b;

                        scanf(" %c%d%d", &q, &a, &b);

                        if (q == 'Q') {
                                int ans = query(1, 1, n, a, b);
                                printf("%d\n", ans);
                        } else {
                                update(1, 1, n, a, b);
                        }

                }

        }
}