#P17210. [2025年海亮中学]在野之壑

    ID: 16369 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-贡献法单调栈计算区间贡献等差数列求和离线查询添加/删除事件树状数组差分树状数组

[2025年海亮中学]在野之壑

题目背景

不顺我意者,当填在野之壑。

题目描述

在野之壑可以分为 nn 个等长的区域,第 ii 个区域的深度为 aia_i。

孙綝会选择一个区间 [l,r][l,r],往此区间中的每个区域都填入等量的不顺我意者。每个区域填入的数量为这些区域深度的最小值。

然而,有时候在野之壑中只有一些区域可用。因此你需要回答 qq 次询问,每次给定一个区间 [L,R][L,R],表示在野之壑中只有 [L,R][L,R] 内的区域可用,也就是选择的区间必须满足 L≤l≤r≤RL\le l\le r\le R。你要回答孙綝,所有的填入方案中,总共填入的不顺我意者数量之和。

输入格式

输入的第一行包含两个正整数 n,qn,q。

输入的第二行包含 nn 个正整数,第 ii 个正整数表示 aia_i。

接下来 qq 行,每行两个正整数 L,RL,R。

输出格式

输出 qq 行,每行包含一个数,表示每次询问的答案。

样例 1 输入

5 5
2 2 1 4 3
1 4
1 5
2 3
2 4
3 5

样例 1 输出

27
48
5
14
19

子任务

对于所有测试数据,保证 1≤n,q≤2×1051\le n,q\le 2\times 10^5,1≤ai≤1081\le a_i\le 10^8,1≤L≤R≤n1\le L\le R\le n。

测试点 n≤n\le q≤q\le
1~2 2020
3~4 10210^2
5~6 500500
7~8 20002000
9~10 50005000 50005000
11~12 2×1052\times 10^5
13~16 10510^5
17~20 2×1052\times 10^5