华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 913|回复: 0
打印 上一主题 下一主题

P3865 【模板】ST表

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2019-11-9 21:29:05 | 只看该作者 回帖奖励 |正序浏览 |阅读模式
https://www.luogu.org/problem/P3865

题目背景
这是一道ST表经典题——静态区间最大值

请注意最大数据时限只有0.8s,数据强度不低,请务必保证你的每次查询复杂度为 O(1)

题目描述
给定一个长度为 N 的数列,和 M 次询问,求出每一次询问的区间内数字的最大值。

输入格式
第一行包含两个整数 N, M ,分别表示数列的长度和询问的个数。

第二行包含 N 个整数依次表示数列的第 i 项。
接下来 M行,每行包含两个整数 li,ri ,表示查询的区间

输出格式
输出包含 M行,每行一个整数,依次表示每一次询问的结果。

输入输出样例
输入
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8
输出
9
9
7
7
9
8
7
9

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 01:59 , Processed in 0.171150 second(s), 24 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表