首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >C++常见几种输入方法评测(int && long long)

C++常见几种输入方法评测(int && long long)

作者头像
全栈程序员站长
发布于 2021-09-29 07:23:29
发布于 2021-09-29 07:23:29
74700
代码可运行
举报
运行总次数:0
代码可运行

B – I Hate It

B – I Hate It

很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。  这让很多学生很反感。 

不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。

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

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
5
6
5
9

这题也是基本的线段树,在上一题的基础上,多了一个求节点最大值的函数,并且把query的查找函数的功能由求这一区间的和改为求这一区间的最大值,中间也一直错,还好现在对线段树的基本代码是熟练了

代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const  int maxn =  200000+100;
int tree[maxn*4],ae[maxn];
void zuida(int node)
{
	tree[node] = max(tree[node*2],tree[node*2+1]);
}
void build(int node, int l, int r)
{
	if(l==r)
	{
		tree[node]=ae[l];
		return ;
	}
	int mid =(l + r)/ 2;
	build(node*2,l,mid);
	build(node*2+1,mid+1,r);
	tree[node]=tree[node*2]+tree[node*2+1];
	zuida(node);
}
void update(int x,int indx,int node, int l, int r)
{
	if(l==r)
	{
		tree[node]=x;
		return ;
	}
	int mid=(l+r)/2;
	if(indx<=mid)  update(x,indx,node*2,l,mid);
	if(indx>mid) update(x,indx,node*2+1,mid+1,r);
	tree[node]=tree[node*2]+tree[node*2+1];
	zuida(node);
}
int query(int x,int y,int node,int l, int r)
{
	if(x<=l&&y>=r)
	{
		return tree[node];
	}
	int mid = (l+r)/2;
	int sum=0;//zaizhe1liangbian
	if(x<=mid) sum=max(sum,query(x, y, node*2,l,mid));
	if(y>mid)  sum=max(sum,query(x, y, node*2+1,mid+1,r));
	return sum;
}
int main()
{
	int m, n;
	int a, b;
	while(cin>>n>>m){
	for(int i=1; i<=n; i++)  scanf("%d",&ae[i]);
	build(1,1,n);
	char s[maxn];
	while(m--)
	{
		scanf("%s",s);
		getchar();
		scanf("%d %d",&a,&b);
		if(s[0]=='Q')
		{
			printf("%d\n",query(a,b,1,1,n));
		}
		if(s[0]=='U')	update(b,a,1,1,n);
		
	}
	}
	return 0;
}

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/114889.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
HDU1754_I Hate It(线段树/单点更新)
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 37915 Accepted Submission(s): 15002
全栈程序员站长
2022/07/07
1840
HDU 1754 I Hate It (段树单点更新)
无论你喜不喜欢,如今须要你做的是,就是依照老师的要求。写一个程序,模拟老师的询问。当然。老师有时候须要更新某位同学的成绩。
全栈程序员站长
2022/07/06
1510
HDUOJ------敌兵布阵
敌兵布阵 Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other) Total Submission(s) : 7   Accepted Submission(s) : 3 Problem Description C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况
Gxjun
2018/03/21
5930
HDU4027
本以为对线段树还是比较熟悉的,但是这题改变了我的想法。 顺着wk的题解做了这题。 拿到手就知道线段树,写完T,这时候我想起来蓝桥杯的线段树也是这样的吧,只不过那题对区间的操作是log,真可笑,当时还以为是cin写跪了,就这题看来,估计也那题没过几组数据,二等奖也在情理之中。 每次都更新到最底下会超时,每个数sqrt几次之后就会成为1,这时再开方是没有意义的,可以剪枝,如果区间长度等于区间和,说明区间没有必要更新,可以直接return。 此外还有好几个WA点 #include<cstdio> #include
triplebee
2018/01/12
5800
HDU 1754 I Hate It(线段树之单点更新,区间最值)
I Hate It Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 70863    Accepted Submission(s): 27424 Problem Description 很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。 这让很多学生很反感。 不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写
Angel_Kitty
2018/04/08
6860
UESTC 1591 An easy problem A【线段树点更新裸题】
An easy problem A Time Limit: 2000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) Submit Status N个数排成一列,Q个询问,每次询问一段区间内的数的极差是多少。 Input 第一行两个整数N(1≤N≤50000),Q(1≤Q≤200000)。接下来一行N个整数a1 a2 a3 ....an,(1≤ai≤1000000000)。接下来Q行,每行两个整数L,R(1≤L≤R≤N)。
Angel_Kitty
2018/04/08
6040
bzoj 4399: 魔法少女LJJ 题解
在森林中见过会动的树,在沙漠中见过会动的仙人掌过后,魔法少女LJJ已经觉得自己见过世界上的所有稀奇古怪的事情了 LJJ感叹道“这里真是个迷人的绿色世界,空气清新、淡雅,到处散发着醉人的奶浆味;小猴在枝头悠来荡去,好不自在;各式各样的鲜花争相开放,各种树枝的枝头挂满沉甸甸的野果;鸟儿的歌声婉转动听,小河里飘着落下的花瓣真是人间仙境” SHY觉得LJJ还是太naive,一天,SHY带着自己心爱的图找到LJJ,对LJJ说:“既然你已经见识过动态树,动态仙人掌了,那么今天就来见识一下动态图吧” LJJ:“要支持什么操作?” SHY:“ 1.新建一个节点,权值为x。 2.连接两个节点。 3.将一个节点a所属于的联通快内权值小于x的所有节点权值变成x。 4.将一个节点a所属于的联通快内权值大于x的所有节点权值变成x。 5.询问一个节点a所属于的联通块内的第k小的权值是多少。 6.询问一个节点a所属联通快内所有节点权值之积与另一个节点b所属联通快内所有节点权值之积的大小。 7.询问a所在联通快内节点的数量 8.若两个节点a,b直接相连,将这条边断开。 9.若节点a存在,将这个点删去。” LJJ:“我可以离线吗?” SHY:“可以,每次操作是不加密的,” LJJ:“我可以暴力吗?” SHY:“自重” LJJ很郁闷,你能帮帮他吗
yzxoi
2022/09/19
3900
HDU 3333 Turing Tree (线段树)
Turing Tree Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4768    Accepted Submission(s): 1686 Problem Description After inventing Turing Tree, 3xian always felt boring when solving problems ab
ShenduCC
2018/04/27
5530
bzoj1396_bzoj3771
大家好,又见面了,我是你们的朋友全栈君。 传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1396 题目大意: 题解:后缀自动机,只出现一次
全栈程序员站长
2022/09/22
1660
bzoj1396_bzoj3771
Simple Problem with Integers POJ – 3468
你有N整数,A1, A2, … , AN..你需要处理两种操作。一种操作是在给定的时间间隔内向每个数字添加一些给定的数字。另一种是要求给定区间内的数字之和。
全栈程序员站长
2021/12/23
2650
P1531 I Hate It
题目背景 很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。这让很多学生很反感。 题目描述 不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩 输入输出格式 输入格式: 第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。学生ID编号分别从1编到N。第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。接下来有M行
attack
2018/04/12
7700
HDU 5634 Rikka with Phi (线段树)
Problem Description Rikka and Yuta are interested in Phi function (which is known as Euler's totient function). Yuta gives Rikka an array  of positive integers, then Yuta makes  queries.   There are three types of queries:  Change  into ,
ShenduCC
2018/04/27
5870
【算法】整体二分初探[通俗易懂]
大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说【算法】整体二分初探,希望能够帮助大家进步!!!
Java架构师必看
2022/01/21
3310
P2023 [AHOI2009]维护序列
老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。 有长为N的数列,不妨设为a1,a2,…,aN 。有如下三种操作形式: (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模P的值。 输入输出格式 输入格式: 第一行两个整数N和P( )。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, ( )。第三行有一个整数M,表示操作总数。从第四行开始每行描述一个操作,输入的操作有以下三种形式: 操作1
attack
2018/04/13
7700
树套树专题——bzoj 3110: [Zjoi2013] K大数查询 &amp; 3236 [Ahoi2013] 作业 题解「建议收藏」
Time Limit: 20 Sec Memory Limit: 512 MB Submit: 978 Solved: 476
全栈程序员站长
2022/07/10
2430
归并树&划分树详解
我们一般用一个结构体数组来保存每个节点,和线段树不同的是,线段树每个节点值保存一段的起始位置和结束位置,而在划分树和递归树中,每个节点的每个元素都是要保存的。为了直观些,我们可以定义一个结构体数组,一个结构体中保存的是一层的元素和到某个节点进入左子树的元素的个数,不同于线段树,我们不能保存一个节点的起始结尾位置,因为随层数的增加,虽然每个结构体保存的元素数目是一定的,但随层数的增加,元素早已被划分到不同的子树中了,而且这数目是指数增加的。
xindoo
2021/01/22
4130
BZOJ 1012: [JSOI2008]最大数maxnumber【线段树单点更新求最值,单调队列,多解】
1012: [JSOI2008]最大数maxnumber Time Limit: 3 Sec  Memory Limit: 162 MB Submit: 10374  Solved: 4535 [Submit][Status][Discuss] Description   现在请求你维护一个数列,要求提供以下两种操作:1、 查询操作。语法:Q L 功能:查询当前数列中末尾L 个数中的最大的数,并输出这个数的值。限制:L不超过当前数列的长度。2、 插入操作。语法:A n 功能:将n加 上t,其中t是最近一
Angel_Kitty
2018/04/09
6220
周练1
操作I i j:翻转i到j之间的01比特(0变成1,1变成0) 操作Q i:询问第i位比特是什么 //线段树
饶文津
2020/06/02
4420
周练1
BZOJ 1568: [JSOI2008]Blue Mary开公司(超哥线段树)
Description image.png Input 第一行 :一个整数N ,表示方案和询问的总数。  接下来N行,每行开头一个单词“Query”或“Project”。  若单词为Query,则后接一个整数T,表示Blue Mary询问第T天的最大收益。  若单词为Project,则后接两个实数S,P,表示该种设计方案第一天的收益S,以及以后每天比上一天多出的收益P。 提示:本题读写数据量可能相当巨大,请选手注意选择高效的文件读写方式。 Output 对于每一个Query,输出一个整数,表
attack
2018/04/12
8810
BZOJ 1568: [JSOI2008]Blue Mary开公司(超哥线段树)
Codeforces #576 div 2 ABCD
A.暴力 #include <bits/stdc++.h> using namespace std; int a[1000005]; int main() { int n,x,y,mi=0; scanf("%d %d %d",&n,&x,&y); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ int fg = 1; for(int j=i-x;j<=i+y;j++){ if(j<1||j>n|
用户2965768
2019/08/14
2390
相关推荐
HDU1754_I Hate It(线段树/单点更新)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档