HDU 1754 线段树(单点更新)

2024-08-28 07:18
文章标签 更新 单点 hdu 线段 1754

本文主要是介绍HDU 1754 线段树(单点更新),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

线段树(interval tree) 是把区间逐次二分得到的一树状结构,它反映了包括归并排序在内的很多分治算法的问题求解方式。

http://acm.hdu.edu.cn/showproblem.php?pid=1754  为例:

I Hate It

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


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


Author
linle


Source
2007省赛集训队练习赛(6)_linle专场


Recommend
lcy   |   We have carefully selected several similar problems for you:   1698  1542  1394  2795  1540 

由于数据过大,普通方法一定会超时,这里我们用线段树解决。 RMQ也行

#include<iostream>
#include <stdio.h>

#define maxn 200005

using namespace std;
struct node
{
int c;
int left,right;
}nod[3*maxn];
int y[maxn];
void build(int i,int l,int r)
{
nod[i].left=l;
nod[i].right=r;
nod[i].c=0;
if(l==r)return;
int mid=(r+l)/2;
build(i<<1,l,mid);//左
build((i<<1)|1,mid+1,r);//右
}
void push_up(int i)
{
nod[i].c=max(nod[i<<1].c,nod[(i<<1)|1].c);
}
void updata(int i,int k,int val)//更新线段树的第k个值为val
{//从上到下更新
if(nod[i].left==k&&nod[i].right==k)
{
nod[i].c=val;
return ;
}
int mid=(nod[i].left+nod[i].right)/2;
if(k<=mid)updata(i<<1,k,val);
else updata((i<<1)|1,k,val);
push_up(i);
}
int query(int i,int l,int r)//查询
{
if(nod[i].left==l&&nod[i].right==r)
return nod[i].c;
int mid=(nod[i].left+nod[i].right)/2;
if(r<=mid)return query(i<<1,l,r);
else if(l>mid)return query((i<<1)|1,l,r);
else return max(query(i<<1,l,mid),query((i<<1)|1,mid+1,r));
}
int main()
{
int n,m,v;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(~scanf("%d%d",&n,&m))
{
build(1,1,n);
for(int i=1;i<=n;i++)
{
scanf("%d",&v);
updata(1,i,v);
}
char s[3];int x,y;
for(int i=1;i<=m;i++)
{
scanf("%s %d %d",&s,&x,&y);
if(s[0]=='Q')
{
printf("%d\n",query(1,x,y));
}
else
{
updata(1,x,y);
}
}
}
return 0;
}



这篇关于HDU 1754 线段树(单点更新)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1114098

相关文章

Security OAuth2 单点登录流程

单点登录(英语:Single sign-on,缩写为 SSO),又译为单一签入,一种对于许多相互关连,但是又是各自独立的软件系统,提供访问控制的属性。当拥有这项属性时,当用户登录时,就可以获取所有系统的访问权限,不用对每个单一系统都逐一登录。这项功能通常是以轻型目录访问协议(LDAP)来实现,在服务器上会将用户信息存储到LDAP数据库中。相同的,单一注销(single sign-off)就是指

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while