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

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 2034 人见人爱A-B

人见人爱A-B Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (J...

33210
来自专栏友弟技术工作室

golang之Struct什么是结构体struct?

最近在复习golang,学习的东西,如果不使用,很快就会忘记。所以,准备复习完golang,做一个练手的小项目,加深对golang的学习。今天开始公司,进入封闭...

6006
来自专栏数据结构与算法

POJ 2001 Shortest Prefixes

Description A prefix of a string is a substring starting at the beginning of th...

2869
来自专栏算法修养

POJ-2329 Nearest number - 2(BFS)

Nearest number - 2 Time Limit: 5000MS Memory Limit: 65536K Total Submis...

2474
来自专栏算法修养

ZOJ 3537 Cake(凸包判定+区间DP)

Cake Time Limit: 1 Second Memory Limit: 32768 KB You want to hold a par...

3789
来自专栏算法修养

HOJ 2985 Wavio Sequence(最长递增子序列以及其O(n*logn)算法)

Wavio Sequence My Tags (Edit) Source : UVA Time limit : 1 sec Memor...

2816
来自专栏一个会写诗的程序员的博客

《Kotlin极简教程》第五章 Kotlin面向对象编程(OOP)一个OOP版本的HelloWorld构造函数传参Data Class定义接口&实现之写pojo bean定一个Rectangle对象封

We frequently create a class to do nothing but hold data. In such a class some s...

2344
来自专栏算法修养

PAT 甲级 1104 sum of Number Segments

1104. Sum of Number Segments (20) 时间限制 200 ms 内存限制 65536 kB 代码长度限制 16...

2835
来自专栏数据结构与算法

洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)

具体来说,每次比较当前后缀和\(S_0\)的lcp,如果长度\(< N\)的话就从不合法的位置继续匹配

1181
来自专栏算法修养

CodeForces 666B World Tour(spfa+枚举)

B. World Tour time limit per test 5 seconds memory limit per test 512 mega...

3384

扫码关注云+社区

领取腾讯云代金券