哈理工OJ 2043 长长长长龙(线段树)

    xiaoxiao2023-05-27  4

    长长长长龙

    Time Limit: 3000 MSMemory Limit: 32768 K

    Total Submit: 247(96 users)Total Accepted: 86(73 users)Rating: Special Judge: No Description

    时间:今天是20XX年,XX月,XX日。

    背景:在这个科技非常发达的今天,某某大型游戏公司的全息游戏马上就要开服了。

    社会影响:这个必然有着XX名字的游戏一出现便引起了很多国家的注意。

    人物:人们如买春运车票般的排起长长长长龙......

    遥想当年一众网游小说模板般的开头。

    现在给出长长长龙中每个人的年龄,问其中第i个人到第j个人中最大的人的年龄是多少。

    Input

    多组输入数据。

    每组数据第一行有2个数n(0<n<50000)代表长长长长龙中一共有n个人,m(0<m<5000)代表一共有m次询问;

    接下来第2行有n个数代表n个人的年龄(0<n<50000)(在这个科技非常发达的今天,想活多久活多久,况且玩游戏当然要从娃娃抓起)。

    多组输入数据。

    每组数据第一行有2个数n(0<n<50000)代表长长长长龙中一共有n个人,m(0<m<5000)代表一共有m次询问;

    接下来第2行有n个数代表n个人的年龄(0<n<50000)(在这个科技非常发达的今天,想活多久活多久,况且玩游戏当然要从娃娃抓起)。

    再接下来的m行:每行有2个数x,y代表询问的区间,第x个人到第y个人。

    Output

    对于每组数据:

    输出每次询问的结果,每个结果占一行。

    Sample Input 5 5 15 19 18 17 16 1 3 1 5 2 5 2 4 3 5 Sample Output 19 19 19 19 18

    SourceHCPC2014校赛训练赛 1

    一道非常水的线段树的题目。

    就是简单的区间最大值的查询。

    下面是AC代码:

    #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; struct node { int le,ri,val; }c[200005]; void build_tree(int l,int r,int root) { c[root].le=l; c[root].ri=r; if(l==r) { scanf("%d",&c[root].val); return; } int mid=(l+r)/2; build_tree(l,mid,root*2); build_tree(mid+1,r,root*2+1); c[root].val=max(c[root*2].val,c[root*2+1].val); } int search_tree(int l,int r,int root) { if(c[root].le==l&&c[root].ri==r) { return c[root].val; } int mid=(c[root].le+c[root].ri)/2; if(mid<l) { return search_tree(l,r,root*2+1); } else if(mid>=r) { return search_tree(l,r,root*2); } else { int maxn=max(search_tree(l,mid,root*2),search_tree(mid+1,r,root*2+1)); return maxn; } } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { memset(c,0,sizeof(c)); build_tree(1,n,1); for(int i=0;i<m;i++) { int a,b; scanf("%d%d",&a,&b); printf("%d\n",search_tree(a,b,1)); } } return 0; }

    转载请注明原文地址: https://ju.6miu.com/read-1260746.html
    最新回复(0)