首页 > 代码库 > HDU 之 I Hate It

HDU 之 I Hate It

2024-07-16 12:18:13   214人阅读

                                                                                I Hate It
Time Limit:3000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit Status

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
 
基础线段树算法的应用（模板题目）
 
#include <stdio.h>#include <string.h>struct N{    int w;}q[550000];int max(int a, int b){    return a>b?a:b;}void build(int x, int k, int left, int right, int rt ){    if(x<left || x>right )    {        return ;    }    if(x==left && x==right )    {        q[rt].w = k;        return;    }    build(x, k, left, (left+right)/2, rt*2 );    build(x, k, (left+right)/2+1, right, rt*2+1 );    q[rt].w = max( q[rt*2].w, q[rt*2+1].w ) ;}int query(int ll, int rr, int left, int right, int rt ){    if(rr<left || ll>right )    {        return 0;    }    if(ll<=left && rr>=right )    {        return q[rt].w;    }    return max(query(ll, rr, left, (left+right)/2, rt*2),query(ll, rr,                                                            (left+right)/2+1,right, rt*2+1 ));}int main(){    int n, m;    int i, j;    char ch;    int ss, dd;    int A; int B;    while(scanf("%d %d", &n, &m)!=EOF)    {        for(i=1; i<=n; i++)        {            scanf("%d%*c", &dd); //cha ru            build(i,dd, 1, n, 1);        }        for(j=0; j<m; j++)        {            scanf("%c %d %d%*c", &ch, &A, &B);            if(ch==‘Q‘)            {                ss = query(A, B, 1, n, 1) ;                printf("%d\n", ss );            }            else if(ch==‘U‘)            {                build(A, B, 1, n, 1);            }        }    }    return 0;}

 别人的写法：

#include <cstdio>#include <cmath>#include <iostream>using namespace std;const int MAXNODE = 524288; // 1<<19const int MAXST = 200001;struct STU{	int grade;	int left,right;}st[MAXNODE];int father[MAXST];void BuildTree(int i,int left,int right){ // i是结点的序号 对应了数组下标	st[i].left = left;	st[i].right = right;	st[i].grade = 0; // 初始化为0	if (left == right)	{		father[left] = i; // 为了更新的时候从下往上 一直到顶		return;	}	BuildTree(i*2, left, (int)floor( (right+left) / 2.0));	BuildTree(i*2+1, (int)floor( (right+left) / 2.0) + 1, right);}void UpdataTree(int ri)// 从下往上更新{		if (ri == 1)	{		return;	}	int fi = ri / 2; // 父结点	int a = st[fi<<1].grade; // 该父结点的两个子结点	int b = st[(fi<<1)+1].grade;	st[fi].grade = (a > b)?(a):(b);	UpdataTree(ri/2);	}int Max;void Query(int i,int l,int r){ // i为区间的序号，四段查询 即四种情况		if (st[i].left == l && st[i].right == r)  // 找到了一个完全重合的区间	{		Max = (Max < st[i].grade)?st[i].grade:(Max);		return ;	}	i = i << 1; // left child of the tree	if (l <= st[i].right) // 左区间有覆盖	{		if (r <= st[i].right) // 全包含于左区间		{			Query(i, l, r);		}		else // 半包含于左区间		{			Query(i, l, st[i].right);		}	}	i += 1; // right child of the tree	if (r >= st[i].left) // 右区间有覆盖	{		if (l >= st[i].left) // 全包含于右区间			Query(i, l, r);		else // 半包含于左区间			Query(i, st[i].left, r);	}}int main(){	int n_s,n_q,igrade; 		while(scanf("%d %d",&n_s,&n_q) != EOF){		BuildTree(1, 1, n_s); 		for (int i= 1 ; i <= n_s; i++)		{			scanf("%d", &igrade );			st[father[i]].grade = igrade; // 底层的无条件更新成绩			UpdataTree(father[i]);		}		while(n_q--)		{			char o[3];int a,b;			scanf("%s %d %d",o,&a,&b);			if ( o[0] == ‘Q‘)			{				Max = 0;				Query(1, a, b);				printf("%d\n",Max);			}			else			{				st[father[a]].grade = b; // 底层的无条件更新成绩				UpdataTree(father[a]);			}		}	}	return 0;}

 


联系
我们