P3722 [AH2017/HNOI2017]影魔

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

题解

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

    推荐的相关题目 显示

    题目背景

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

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

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

    题目描述

    奈文摩尔有 $n$ 个灵魂,他们在影魔宽广的体内可以排成一排,从左至右标号 $1$ 到 $n$。第 $i$ 个灵魂的战斗力为 $k_i$,灵魂们以点对的形式为影魔提供攻击力。对于灵魂对 $i, j\ (i<j)$ 来说,若不存在 $k_s\ (i<s<j)$ 大于 $k_i$ 或者 $k_j$,则会为影魔提供 $p_1$ 的攻击力。另一种情况,令 $c$ 为 $k_{i + 1}, k_{i + 2}, \cdots, k_{j -1}$ 的最大值,若 $c$ 满足:$k_i < c < k_j$,或者 $k_j < c < k_i$,则会为影魔提供 $p_2$ 的攻击力,当这样的 $c$ 不存在时,自然不会提供这 $p_2$ 的攻击力;其他情况的点对,均不会为影魔提供攻击力。

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

    顺带一提,灵魂的战斗力组成一个 $1$ 到 $n$ 的排列:$k_1, k_1, \cdots, k_n$。

    输入输出格式

    输入格式:

    第一行四个整数 $n,m,p_1,p_2$。

    第二行 $n$ 个整数 $k_1, k_2,\cdots, k_n$。

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

    输出格式:

    共输出 $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\le n, m\le 500$。

    另有 $30\%$ 的数据,$p_1 = 2p_2$。

    对于 $100\%$ 的数据,$1\le n,m\le 200000, 1\le p_1, p_2\le 1000$。

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