首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >UESTC 1591 An easy problem A【线段树点更新裸题】

UESTC 1591 An easy problem A【线段树点更新裸题】

作者头像
Angel_Kitty
发布2018-04-08 17:12:06
5490
发布2018-04-08 17:12:06
举报

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)。

Output

对于每个询问输出一行,一个整数表示区间内的极差。

Sample input and output

Sample Input

Sample Output

5 3 3 2 7 9 10 1 5 2 3 3 5

8 5 3

题目链接:http://acm.uestc.edu.cn/#/contest/show/155

分析:线段树点更新裸题,继续复习线段树,这题要算的是极差,只需要建树和查询两部分,无需更新,所以建树的时候只要去求最大值和最小值即可,然后极差一减得出答案!

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=200020;
 4 struct Node
 5 {
 6     int l,r,minn,maxn;
 7 }tree[N<<2];
 8 void build(int l,int r,int pos)
 9 {
10     tree[pos].l=l;
11     tree[pos].r=r;
12     if(l==r)
13     {
14         scanf("%d",&tree[pos].maxn);
15         tree[pos].minn=tree[pos].maxn;
16         return;
17     }
18     int mid=(l+r)/2;
19     build(l,mid,pos*2);
20     build(mid+1,r,pos*2+1);
21     tree[pos].maxn=max(tree[pos*2].maxn,tree[pos*2+1].maxn);
22     tree[pos].minn=min(tree[pos*2].minn,tree[pos*2+1].minn);
23 }
24 int query1(int l,int r,int pos)
25 {
26     if(tree[pos].l==l&&tree[pos].r==r)
27         return tree[pos].minn;
28     int mid=(tree[pos].l+tree[pos].r)/2;
29     if(r<=mid)
30         return query1(l,r,pos*2);
31     else if(l>mid)
32         return query1(l,r,pos*2+1);
33     else return min(query1(l,mid,pos*2),query1(mid+1,r,pos*2+1));
34 }
35 int query2(int l,int r,int pos)
36 {
37     if(tree[pos].l==l&&tree[pos].r==r)
38         return tree[pos].maxn;
39     int mid=(tree[pos].l+tree[pos].r)/2;
40     if(r<=mid)
41         return query2(l,r,pos*2);
42     else if(l>mid)
43         return query2(l,r,pos*2+1);
44     else return max(query2(l,mid,pos*2),query2(mid+1,r,pos*2+1));
45 }
46 int main()
47 {
48     int x,y;
49     scanf("%d%d",&x,&y);
50     build(1,x,1);
51     while(y--)
52     {
53         int p,q;
54         scanf("%d%d",&p,&q);
55         printf("%d\n",query2(p,q,1)-query1(p,q,1));
56     }
57     return 0;
58 }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-05-03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • An easy problem A
    • Input
      • Output
        • Sample input and output
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档