POJ 3264 Balanced Lineup (线段树单点更新 区间查询)

2024-03-20 14:32

本文主要是介绍POJ 3264 Balanced Lineup (线段树单点更新 区间查询),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


Balanced Lineup
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 36820 Accepted: 17244
Case Time Limit: 2000MS

Description

For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

Input

Line 1: Two space-separated integers, N and Q.
Lines 2.. N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2.. N+ Q+1: Two integers A and B (1 ≤ ABN), representing the range of cows from A to B inclusive.

Output

Lines 1.. Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

Sample Input

6 3
1
7
3
4
2
5
1 5
4 6
2 2

Sample Output

6
3
0

Source

USACO 2007 January Silver

题目链接:http://poj.org/problem?id=3264

题目大意:给一组有序数列,求区间内最大值减最小值的值

题目分析:裸线段树单点更新,交的时候C++速度比G++快一倍

#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
using namespace std;
int const INF = 0x3fffffff;
int const MAX = 50005;
int a[MAX], ma, mi;
struct node
{int l, r;int mi, ma;int mid(){return (l + r) / 2;}
}t[3 * MAX];void push_up(int rt)
{t[rt].ma = max(t[rt << 1].ma, t[rt << 1 | 1].ma);t[rt].mi = min(t[rt << 1].mi, t[rt << 1 | 1].mi);
}void Build(int l, int r, int rt)
{t[rt].l = l;t[rt].r = r;if(l == r){t[rt].ma = t[rt].mi = a[l];return;}else{int mid = t[rt].mid();Build(lson);Build(rson);push_up(rt);}
}void Query(int l, int r, int rt)
{if(t[rt].l == l && t[rt].r == r){ma = max(t[rt].ma, ma);mi = min(t[rt].mi, mi);return;}else{int mid = t[rt].mid();if(r <= mid)Query(l, r, rt << 1);else if(l > mid)Query(l, r, rt << 1 | 1);else{Query(lson);Query(rson);}}
}int main()
{int n, m;scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++)scanf("%d", &a[i]);Build(1, n, 1);for(int i = 1; i <= m; i++){int l, r;scanf("%d %d", &l, &r);ma = -INF;mi = INF;Query(l, r, 1);printf("%d\n", ma - mi);}
}




这篇关于POJ 3264 Balanced Lineup (线段树单点更新 区间查询)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/829777

相关文章

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

MYSQL查询结果实现发送给客户端

《MYSQL查询结果实现发送给客户端》:本文主要介绍MYSQL查询结果实现发送给客户端方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql取数据和发数据的流程(边读边发)Sending to clientSending DataLRU(Least Rec

MySQL复杂SQL之多表联查/子查询详细介绍(最新整理)

《MySQL复杂SQL之多表联查/子查询详细介绍(最新整理)》掌握多表联查(INNERJOIN,LEFTJOIN,RIGHTJOIN,FULLJOIN)和子查询(标量、列、行、表子查询、相关/非相关、... 目录第一部分:多表联查 (JOIN Operations)1. 连接的类型 (JOIN Types)

python编写朋克风格的天气查询程序

《python编写朋克风格的天气查询程序》这篇文章主要为大家详细介绍了一个基于Python的桌面应用程序,使用了tkinter库来创建图形用户界面并通过requests库调用Open-MeteoAPI... 目录工具介绍工具使用说明python脚本内容如何运行脚本工具介绍这个天气查询工具是一个基于 Pyt

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

在Java中基于Geotools对PostGIS数据库的空间查询实践教程

《在Java中基于Geotools对PostGIS数据库的空间查询实践教程》本文将深入探讨这一实践,从连接配置到复杂空间查询操作,包括点查询、区域范围查询以及空间关系判断等,全方位展示如何在Java环... 目录前言一、相关技术背景介绍1、评价对象AOI2、数据处理流程二、对AOI空间范围查询实践1、空间查

MySQL基本查询示例总结

《MySQL基本查询示例总结》:本文主要介绍MySQL基本查询示例总结,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Create插入替换Retrieve(读取)select(确定列)where条件(确定行)null查询order by语句li

Oracle 通过 ROWID 批量更新表的方法

《Oracle通过ROWID批量更新表的方法》在Oracle数据库中,使用ROWID进行批量更新是一种高效的更新方法,因为它直接定位到物理行位置,避免了通过索引查找的开销,下面给大家介绍Orac... 目录oracle 通过 ROWID 批量更新表ROWID 基本概念性能优化建议性能UoTrFPH优化建议注