P3865 【模板】ST表

    • 4.1K通过
    • 9.2K提交
  • 题目提供者 HansBug 站长团
  • 评测方式 云端评测
  • 标签 st表,稀疏表 树状数组 线段树 O2优化 高性能
  • 难度 普及/提高-
  • 时空限制 100ms-800ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

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

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

    题目描述

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

    输入输出格式

    输入格式:

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

    第二行包含 $ N $ 个整数(记为 $ a_i $ ),依次表示数列的第 $i $ 项。

    接下来 $ M $ 行,每行包含两个整数 $l_i, r_i $ ,表示查询的区间为 $[ l_i, r_i] $

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    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
    输出样例#1: 复制
    9
    9
    7
    7
    9
    8
    7
    9

    说明

    对于30%的数据,满足: $ 1 \leq N, M \leq 10 $

    对于70%的数据,满足: $ 1 \leq N, M \leq {10}^5 $

    对于100%的数据,满足: $ 1 \leq N \leq {10}^5, 1 \leq M \leq {10}^6, a_i \in [0, {10}^9], 1 \leq l_i \leq r_i \leq N $

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。