P3722 [AH2017/HNOI2017]影魔

    • 175通过
    • 459提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 各省省选 2017 湖南 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 512MB

题解

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

    推荐的相关题目 显示

    题目背景

    影魔,奈文摩尔,据说有着一个诗人的灵魂。 事实上,他吞噬的诗人灵魂早已成千上万。

    千百年来,他收集了各式各样的灵魂,包括诗人、 牧师、 帝王、 乞丐、 奴隶、 罪人,当然,还有英雄。

    题目描述

    每一个灵魂,都有着自己的战斗力,而影魔,靠这些战斗力提升自己的攻击。

    奈文摩尔有 n 个灵魂,他们在影魔宽广的体内可以排成一排,从左至右标号 1 到 n。第 i个灵魂的战斗力为 k[i],灵魂们以点对的形式为影魔提供攻击力,对于灵魂对 i, j(i<j)来说,若不存在 ks大于 k[i]或者 k[j],则会为影魔提供 p1 的攻击力(可理解为: 当 j=i+1 时,因为不存在满足 i<s<j 的 s,从而 k[s]不存在,这时提供 p1 的攻击力;当 j>i+1 时,若max{k[s]|i<s<j}<=min{k[i],k[j]} , 则 提 供 p1 的 攻 击 力 ); 另 一 种 情 况 , 令 c 为k[i+1],k[i+2],k[i+3]……k[j-1]的最大值,若 c 满足: k[i]<c<k[j],或者 k[j]<c<k[i],则会为影魔提供 p2 的攻击力,当这样的 c 不存在时,自然不会提供这 p2 的攻击力;其他情况的点对,均不会为影魔提供攻击力。

    影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了,他想知道,对于任意一段区间[a,b], 1<=a<b<=n,位于这些区间中的灵魂对会为影魔提供多少攻击力,即考虑 所有满足a<=i<j<=b 的灵魂对 i,j 提供的攻击力之和。

    顺带一提,灵魂的战斗力组成一个 1 到 n 的排列: k[1],k[2],…,k[n]。

    输入输出格式

    输入格式:

    输入文件名为 sf.in。

    第一行 n,m,p1,p2

    第二行 n 个数: k[1],k[2],…,k[n]

    接下来 m 行, 每行两个数 a,b, 表示询问区间[a,b]中的灵魂对会为影魔提供多少攻击力。

    输出格式:

    输出文件名为 sf.out

    共输出 m 行,每行一个答案,依次对应 m 个询问。

    输入输出样例

    输入样例#1: 复制
    10 5 2 3
    7 9 5 1 3 10 6 8 2 4
    1 7
    1 9
    1 3
    5 9
    1 5
    输出样例#1: 复制
    30
    39
    4
    13
    16

    说明

    30%: 1<= n,m <= 500。

    另 30%: p1=2*p2。

    100%:1 <= n,m <= 200000; 1 <= p1,p2 <= 1000。

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