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表操作与查询,涵盖创建、修改、复制表语法,基本查询结构及WHERE、GROUPBY等子句,本文结合实例代码给大家介绍的非常详细,感兴趣的朋友跟随... 目录01.表的操作1.1表操作概览1.2创建表1.3修改表1.4复制表02.基本查询操作2.1 SE

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

MySQL追踪数据库表更新操作来源的全面指南

《MySQL追踪数据库表更新操作来源的全面指南》本文将以一个具体问题为例,如何监测哪个IP来源对数据库表statistics_test进行了UPDATE操作,文内探讨了多种方法,并提供了详细的代码... 目录引言1. 为什么需要监控数据库更新操作2. 方法1:启用数据库审计日志(1)mysql/mariad

XML重复查询一条Sql语句的解决方法

《XML重复查询一条Sql语句的解决方法》文章分析了XML重复查询与日志失效问题,指出因DTO缺少@Data注解导致日志无法格式化、空指针风险及参数穿透,进而引发性能灾难,解决方案为在Controll... 目录一、核心问题:从SQL重复执行到日志失效二、根因剖析:DTO断裂引发的级联故障三、解决方案:修复

mysql查询使用_rowid虚拟列的示例

《mysql查询使用_rowid虚拟列的示例》MySQL中,_rowid是InnoDB虚拟列,用于无主键表的行ID查询,若存在主键或唯一列,则指向其,否则使用隐藏ID(不稳定),推荐使用ROW_NUM... 目录1. 基本查询(适用于没有主键的表)2. 检查表是否支持 _rowid3. 注意事项4. 最佳实

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