首页 > 代码库 > AC日记——I Hate It 洛谷 P1531
AC日记——I Hate It 洛谷 P1531
题目背景
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。
题目描述
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩
输入输出格式
输入格式：
第一行，有两个正整数 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‘的时候，表示这是一条更新操作，如果当前A学生的成绩低于B，则把ID为A的学生的成绩更改为B，否则不改动。
输出格式：
对于每一次询问操作，在一行里面输出最高成绩
输入输出样例
输入样例#1：
5 61 2 3 4 5Q 1 5U 3 6Q 3 4Q 4 5U 2 9Q 1 5
输出样例#1：
5659
思路：
裸线段树
来，上代码：
#include <cstdio>#include <iostream>#include <algorithm>using namespace std;class T_tree { public: int l,r,dis,flag,mid; bool if_; void mid_() { mid=(l+r)>>1; } void flag_() { flag=0; } void dis_() { scanf("%d",&dis); }};class T_tree tree[200000*4+1];int n,m;inline int max(int SOME_THING_1,int SOME_THING_2){ if(SOME_THING_1>SOME_THING_2) return SOME_THING_1; else return SOME_THING_2;}inline void tree_up(int now){ tree[now].dis=max(tree[now<<1].dis,tree[now<<1|1].dis);}void tree_build(int now,int l,int r){ tree[now].l=l,tree[now].r=r; if(l==r) { tree[now].dis_(); return ; } tree[now].mid_(); tree_build(now<<1,l,tree[now].mid); tree_build(now<<1|1,tree[now].mid+1,r); tree_up(now);}int tree_query(int now,int l,int r){ if(tree[now].l==l&&tree[now].r==r) { return tree[now].dis; } if(l>tree[now].mid) return tree_query(now<<1|1,l,r); else if(r<=tree[now].mid) return tree_query(now<<1,l,r); else { int sum_=-2333333; sum_=max(tree_query(now<<1,l,tree[now].mid),sum_); sum_=max(tree_query(now<<1|1,tree[now].mid+1,r),sum_); return sum_; }}void tree_change(int now,int to,int dis){ if(tree[now].l==to&&tree[now].l==tree[now].r) { tree[now].dis=max(tree[now].dis,dis); return ; } if(tree[now].mid<to) tree_change(now<<1|1,to,dis); else tree_change(now<<1,to,dis); tree_up(now);}int main(){ scanf("%d%d",&n,&m); tree_build(1,1,n); char ty; int l,r; for(int i=1;i<=m;i++) { cin>>ty; scanf("%d%d",&l,&r); if(ty==‘Q‘) { printf("%d\n",tree_query(1,l,r)); } else { tree_change(1,l,r); } } return 0;}
AC日记——I Hate It 洛谷 P1531
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。