【ACM】【线段树】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

对于每一次询问操作,在一行里面输出最高成绩。

以下我的代码

 #include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 200000 + 10;
int a[maxn];
int maximum[maxn << 2];
void build(int l, int r, int rt);
void pushup(int rt);
void update(int L, int C, int l, int r, int rt);
int query(int L, int R, int l, int r, int rt);
int main()
{
#ifdef local
    freopen("Text.txt", "r", stdin);
#endif // local

    int N, M;
    while (scanf("%d%d", &N, &M) != EOF){
        for (int i = 1; i <= N; i++){
            scanf("%d", &a[i]);
        }
        build(1, N, 1);
        char c;
        int A, B;
        while (M--){
            scanf("%c %d %d", &c,&A,&B);
            if (c == 'U'){
                update(A, B, 1, N, 1);
            }
            else if (c == 'Q'){
                printf("%d\n", query(A, B, 1, N, 1));
            }
        }
    }
    return 0;
}
void build(int l, int r, int rt)
{
    if (l == r){
        maximum[rt] = a[l];
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    pushup(rt);
}
void pushup(int rt)
{
    maximum[rt] = max(maximum[rt << 1], maximum[rt << 1 | 1]);
}
void update(int L, int C, int l, int r, int rt)
{
    if (l == r){
        maximum[rt] = C;
        return;
    }
    int m = (l + r) >> 1;
    if (L <= m){//向左子树递归
        update(L, C, l, m, rt << 1);
    }
    else
        update(L, C, m + 1, r, rt << 1 | 1);
    pushup(rt);
}
int query(int L, int R, int l, int r, int rt)
{
    if (l<=L&&r>=R){//这里错了,还是不怎么懂惹QAQ(which means目标区间被操作区间包含
        return maximum[rt];
    }
    int m = (l + r) >> 1;
    int ans = 0;
    if (L <= m){
        ans=max(ans,query(L, R, l, m, rt << 1));
    }
    if (m < R){
        ans=max(ans,query(L, R, m + 1, r, rt << 1 | 1));
    }
}

求教为什么会超时嘤嘤嘤

0

1个回答

1
weixin_39936277
newdawnfades 终于弄懂了TVT谢谢您
10 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
I Hate It(线段树入门)
线段树(不包含区间更新)rnrnrn       线段树是一棵二叉树,树中的每一个结点表示了一个区间[a,b]。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点[a,b],编号为x,其左儿子表示的区间为[a,(a+b)/2],编号为2*x,右儿子表示的区间为[(a+b)/2+1,b],编号为2*x+1。rnrnrnrn一般来说,线段树是一种数据结构模板,通常包含以下五个部分:rnb
HDU - 1754 ——I Hate It (线段树的单点最大值)
很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。 这让很多学生很反感。 不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。 Input 本题目包含多组测试,请处理到文件结束。 在每个测试的第一行,有两个正整数 N 和 M ( 0&amp;lt;N&amp;lt;=20...
I Hate It HDU - 1754(线段树-单点更新模板题)
I Hate Itnn HDU - 1754nn很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。 n这让很多学生很反感。 n不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。nnInputnn本题目包含多组测试,请处理到文件结束。 n在每个测试的第一行,有两个正整数 N 和 M ( 0&amp;lt;...
HDU 1754 I Hate It (线段树,模板)
Descriptionn 很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。n n 这让很多学生很反感。n n 不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。n Inputn 本题目包含多组测试,请处理到文件结束。n n 在每个测试的第一行,有两个正整数 N 和 M ( 0Ou
【ACM】【线段树】I Hate It
# Inputn 本题目包含多组测试,请处理到文件结束。n 在每个测试的第一行,有两个正整数 N 和 M ( 0n#include nusing namespace std;nconst int maxn = 200000 + 10;nint a[maxn];nint maximum[maxn << 2];nvoid build(int l, int r, int rt);nvoid pushup(int rt);nvoid update(int L, int C, int l, int r, int rt);nint query(int L, int R, int l, int r, int rt);nint main()nn#ifdef localn freopen("Text.txt", "r", stdin);n#endif // localnn int N, M;n while (scanf("%d%d", &N, &M) != EOF)n for (int i = 1; i <= N; i++)n scanf("%d", &a[i]);n n build(1, N, 1);n char c;n int A, B;n while (M--)n scanf("%c %d %d", &c,&A,&B);n if (c == 'U')n update(A, B, 1, N, 1);n n else if (c == 'Q')n printf("%d\n", query(A, B, 1, N, 1));n n n n return 0;nnvoid build(int l, int r, int rt)nn if (l == r)n maximum[rt] = a[l];n return;n n int m = (l + r) >> 1;n build(l, m, rt << 1);n build(m + 1, r, rt << 1 | 1);n pushup(rt);nnvoid pushup(int rt)nn maximum[rt] = max(maximum[rt << 1], maximum[rt << 1 | 1]);nnvoid update(int L, int C, int l, int r, int rt)nn if (l == r)n maximum[rt] = C;n return;n n int m = (l + r) >> 1;n if (L <= m)//向左子树递归n update(L, C, l, m, rt << 1);n n elsen update(L, C, m + 1, r, rt << 1 | 1);n pushup(rt);nnint query(int L, int R, int l, int r, int rt)nn if (l<=L&&r>=R)//这里错了,还是不怎么懂惹QAQ(which means目标区间被操作区间包含n return maximum[rt];n n int m = (l + r) >> 1;n int ans = 0;n if (L <= m)n ans=max(ans,query(L, R, l, m, rt << 1));n n if (m < R)n ans=max(ans,query(L, R, m + 1, r, rt << 1 | 1));n nn```n求教为什么会超时嘤嘤嘤nn
线段树的各种板子
很明显不是刚刚写的线段树线段树是什么呢?线段树啊… n大概就是一颗可爱的二叉树… n它的每一个节点代表着一个区间的一个性质… n(比如说最大值最小值还有和之类的…) n然后因为是二叉树所以有很多奇奇怪怪的东西都来了… n至于有什么也不打算细讲。 n一个点x的左儿子就是x*2呀,右儿子就是x*2+1呀 n还有在线段树里面 叶儿子或者说叶节点 所代表的区间是1呀。 n想象成初中历史书上的周朝等级制度图就
I Hate It(基本线段树)
I Hate ItnnTime Limit : 9000/3000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)nnTotal Submission(s) : 24   Accepted Submission(s) : 7nnProblem Descriptionnn很多学校流行一种比较的习惯。老师们很喜欢询问,
线段树 树状数组 数据结构
线段树 树状数组 数据结构 线段树 树状数组 数据结构 acm 线段树 树状数组 数据结构 线段树 树状数组 数据结构 acm 线段树 树状数组 数据结构 线段树 树状数组 数据结构 acm 线段树 树状数组 数据结构 线段树 树状数组 数据结构 acm 线段树 树状数组 数据结构 线段树 树状数组 数据结构 acm
I Hate It 【线段树 or 分块】
I Hate It n很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。 n这让很多学生很反感。 nn不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。 nInput n本题目包含多组测试,请处理到文件结束。 n在每个测试的第一行,有两个正整数 N 和 M ( 0 &amp;lt; N &amp;lt; ...
HDU1754——I Hate It(线段树)
I Hate Itrn点我点我点我http://acm.hdu.edu.cn/showproblem.php?pid=1754rnTime Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)rnTotal Submission(s): 64616    Accepted Submission(
I Hate It 线段树模板
很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。 n这让很多学生很反感。 nn不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。 nInput本题目包含多组测试,请处理到文件结束。 n在每个测试的第一行,有两个正整数 N 和 M ( 0n学生ID编号分别从1编到N。 n第二行包含
P1531 I Hate It(线段树)
题见洛谷#include<iostream>n#include<cstdio>n#include<algorithm>n#include<string>n#include<cstring>n#define MAXN 200000 nusing namespace std;nint a0[MAXN+5],st[MAXN*4+5]; nvoid build(int o,int l,int r)n{
I Hate It【线段树 最值】
I Hate It nTime Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) nTotal Submission(s): 86070 Accepted Submission(s): 33036Problem Description n很多学校流行一种比较的习惯。老师们很喜欢询问,从某
【HDU1754】I Hate It(线段树)
题:http://acm.hdu.edu.cn/showproblem.php?pid=1754I Hate ItTime Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) nTotal Submission(s): 82147 Accepted Submission(s): 31582
线段树i hate it
I Hate ItrnrnTime Limit : 9000/3000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)rnrnTotal Submission(s) : 70   Accepted Submission(s) : 24rnrnProblem Descriptionrnrn很多学校流行一种比较的习惯。老师们很喜欢询问
I Hate It 【线段树】
题目链接:HDU-1754n[kuangbin带你飞]专题七 线段树nn题目描述:n很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。n这让很多学生很反感。n不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。nnn思路n单点修改,区间询问最值,典型的RMQ问题;这里用线段树写的;n树状数组和RM...
线段树——F - I Hate It
很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。 n这让很多学生很反感。 n不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。nnInputnn本题目包含多组测试,请处理到文件结束。 n在每个测试的第一行,有两个正整数 N 和 M ( 0&amp;lt;N&amp;lt;=200000,0&amp;lt;M&amp;lt;5...
线段树——I Hate it
省赛结束了是时候开始学习新的算法了,不过我一直都想学习线段树,所以今天开始学习线段树算法,先来发基础线段树题目开开胃!rnrnrn题目:rnrnProblem Descriptionrn很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。rn这让很多学生很反感。rnrn不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需
B - I Hate It ——线段树
Think: n1知识点:线段树——区间最值+单点更新 n2反思:注意数组不要越界,开四倍即可vjudge题目链接B - I Hate It n很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。n这让很多学生很反感。n不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。Inputn 本题目包含
B - I Hate It (线段树)
很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。n这让很多学生很反感。n不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。nnInputnn本题目包含多组测试,请处理到文件结束。n在每个测试的第一行,有两个正整数 N 和 M ( 0&amp;lt;N&amp;lt;=200000,0&amp;lt;M&amp;lt;5000...
I Hate It(线段树)
rnI Hate ItrnTime Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 28169    Accepted Submission(s): 11168rnProblem Descriptionrn很多学校流行一种比较的习惯。老师们很喜欢询问...
acm程序设计竞赛_培训_线段树
浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树
URAL 1989 Subpalindromes(回文串 线段树 多项式hash)
1989. SubpalindromesnTime limit: 0.5 secondnMemory limit: 64 MBnnnnYou have a string and queries of two types:nnreplace i’th character of the string by character a;check if substring sj...sk i
HDU4578-Transformation (线段树多种区间操作)
题意:一开始有n个为0的数,一共有四种操作:区间[l,r]内的数全部加c。区间[l,r]内的数全部乘c。区间[l,r]内的数全部初始为c。询问区间[l,r]内所有数的P次方之和。nn分析:因为操作种数较多,不可能递归到底层然后进行计算,只需判断这个区间的元素是否完全相同,然后直接进行计算即可。nn参考博客:https://blog.csdn.net/a664607530/article/detai...
B - I Hate It(单点更新)(区间求最大值)
B - I Hate Itrnrn很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。 rn这让很多学生很反感。 rnrn不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。 rnrnInput 本题目包含多组测试,请处理到文件结束。 rn在每个测试的第一行,有两个正整数 N 和 M ( 0rn学生
HDU - 1754 B - I Hate It - 线段树 单点覆盖+区间查询
代码:#include&amp;lt;bits/stdc++.h&amp;gt;nusing namespace std;ntypedef long long ll;nconst int maxn = 2e5+10;nll arr[maxn];nstruct SegTreen{n ll Max[maxn&amp;lt;&amp;lt;2],cnt[maxn&amp;lt;&amp;lt;2],lz[maxn&amp;lt;&amp;lt;2];n ...
HDU-1754 D - I Hate It 【线段树模板题】
链接:点这里nn题意:给你多组数据,每一组n,m,有n个学生,m次查询,其中Q a b表示查询在a到b区间里的最高分,U a b表示更新a学生的成绩为b。nn思路:裸的线段树,记住开数组要*4,hdu是多组输入。我wa了好多次的原因竟然是...query的板子写错了。找区间最大值应该左边和右边分别遍历,我写成了if...else关系nnn#include&lt;iostream&gt;n#incl...
杭电acm 1754I Hate It(线段树)
I Hate ItnTime Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)nTotal Submission(s): 77427    Accepted Submission(s): 29793nnnnProblem Descriptionnn很多学校流行一种比较的习惯。
【HDU - 1698】 Just a Hook(线段树模板 区间覆盖更新(laz标记) + 区间和查询 )
题干:nnIn the game of DotA, Pudge’s meat hook is actually the most horrible thing for most of the heroes. The hook is made up of several consecutive metallic sticks which are of the same length. nnnnnNo...
ACM竞赛算法之线段树
线段树是一个很重要的数据结构,而且在算法竞赛中用处也十分巨大,但很多人往往认为线段树是一个算法,可以完成某些功能,但是实际上完全可以把它看成是一个容器,用来执行的操作可以按照需求修改nnnn首先思考如下问题: n思考一、现在如果有一个长度为n的序列,有m次操作,操作中包含区间求和,某点修改,并且n和m特别大 n思考二、现在给你一个长度为n的序列,有m次操作,操作中仅包含求区间内最大值或最小值的问题
【hdu】【线段树入门】I Hate It
Problem Description很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。 n这让很多学生很反感。不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。Input本题目包含多组测试,请处理到文件结束。 n在每个测试的第一行,有两个正整数 N 和 M ( 0Output对于每一次询问操作,
HDU1754 I HATE IT(简单的线段树)
题目:I HATE IT 很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。Input本题目包含多组测试,请处理到文件结束。 在每个测试的第一行,有两个正整数 N 和 M ( 0&amp;lt;N&amp;lt;=200000,0&amp;lt;M&amp;lt;5000 ),...
HDU1754——I Hate It(线段树入门)
题目连接:I Hate Itrn思路:线段树基操rn我被数组疯狂卡T,所以,要开大4倍的题目数组。。。rn#include&lt;stdio.h&gt;rn#include&lt;iostream&gt;rn#include&lt;map&gt;rn#include&lt;algorithm&gt;rn#include&lt;cstring&gt;rn#include&lt;string.h&gt;rn#inclu...
7_22_N题 I Hate It(线段树)
7_22_N题 I Hate It题意给出一些学生的成绩,老师会询问,某一段学生中最高的成绩,或修改某同学的成绩。思路求区间最大值和单点更新,线段树##include <bits/stdc++.h>#define lson l,mid,rt<<1n#define rson mid+1,r,rt<<1|1nconst int maxn = 2e5+10;nusing namespace std;nch
线段树入门理解
线段树入门理解
HDU1754 - I Hate It (基础线段树)
题目链接思路线段树的基本应用,区间查询,单点更新代码#include <algorithm>n#include <iostream>n#include <cstdlib>n#include <cstdio>n#define lson tree[root].lsn#define rson tree[root].rsusing namespace std;nconst int maxn = 200000
洛谷P1531 I Hate It(线段树)
I Hate It题目背景很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。这让很多学生很反感。题目描述不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩输入输出格式输入格式: n第一行,有两个正整数 N 和 M ( 0#include <cstdio>n#include <string>n#inc
I Hate It (用线段树解决)
这道题用到了线段树,之前看了相关的视频,对算法思路基本理解,但代码实现还有些困难,后来问了学长,自己又研究了一波,最后终于搞明白了。nn线段树视频地址:https://www.bilibili.com/video/av44354587nn点击此处查看题目nn线段树如图所示:nnnn完整代码:nn#include &lt;iostream&gt;n#include &lt;cstdio&gt;n#i...
2018 ACM/ICPC 北京赛区网络赛 D 80 Days 线段树
http://hihocoder.com/problemset/problem/1831?sid=1390457nn描述nn80 Days is an interesting game based on Jules Verne's science fiction &quot;Around the World in Eighty Days&quot;. In this game, you have to manage ...
线段树 与 信息学竞赛 pdf 非常有用 acm
线段树与信息学竞赛,线段树应用 pdf acm初步
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 人工智能i教程 i产品经理培训学什么意思