P3246 [HNOI2016]序列

    • 86通过
    • 471提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 st表,稀疏表 前缀和 2016 湖南 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 512MB

题解

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

    推荐的相关题目 显示

    题目描述

    给定长度为n的序列:a1,a2,...,an,记为a[1:n]。类似地,a[l:r](1<=l<=r<=N)是指序列:al,al+1,...,ar-1,ar。若1<=l<=s<=t<=r<=n,则称a[s:t]是a[l:r]的子序列。现在有q个询问,每个询问给定两个数l和r,1<=l<=r<=n,求a[l:r]的子序列的最小值之和。例如,给定序列5,2,4,1,3,询问给定的两个数为1和3,那么a[1:3]有6个子序列a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3],这6个子序列的最小值之和为5+2+4+2+2+2=17。

    输入输出格式

    输入格式:

    输入文件的第一行包含两个整数n和q,分别代表序列长度和询问数。接下来一行,包含n个整数,以空格隔开,第i个整数为ai,即序列第i个元素的值。接下来q行,每行包含两个整数l和r,代表一次询问。

    输出格式:

    对于每次询问,输出一行,代表询问的答案。

    输入输出样例

    输入样例#1: 复制
    5 5
    5 2 4 1 3
    1 5
    1 3
    2 4
    3 5
    2 5
    输出样例#1: 复制
    28 
    17 
    11 
    11 
    17

    说明

    1 <=N,Q <= 100000,|Ai| <= 10^9

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