← 返回题目列表

AtCoder · awc0106_e

E. 货物稳定安排

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥负责管理仓库中的包裹。有 N 包裹在仓库里排成一排,从左到右为包裹编号 1,包装 2, ..., 包 N.

每包 i 的权重由整数表示 A_i.

Takahashi 执行将连续包裹堆叠到货架上的任务。一个区间 放置在货架上的包裹 [l, r] 如果满足以下条件,则称为“稳定排列”:

  • 对于每个包 j 在区间 (l < j \leq r), 至少存在一个包 i 这样 l \leq i < j 和 A_i \leq A_j.

这意味着每个包裹可以使用其左侧的间隔内的一些包裹作为支撑来稳定地堆叠。一个包裹可以稳定地堆叠在具有相同或更轻重量的另一个包裹的顶部。最左边的包裹直接放在货架底部,因此不受此条件的影响。

青木问高桥 Q 问题。对于每个问题,有一个区间 给出了 [L_k, R_k] 。求完全包含在该区间内且形成稳定排列的连续子区间的数量。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_k \leq R_k \leq N (1 \leq k \leq Q)
  • 所有输入均为整数

输入

N Q
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 第一行包含 N,包裹数量,以及 Q,问题数,以空格分隔。
  • 第二行包含 A_1, A_2, \ldots, A_N,每个包裹的重量,以空格分隔。
  • 以下 Q 行包含间隔 [L_k, R_k] 每个问题。
  • 的 (2 + k)第行包含左端点 L_k 和右端点 R_k 的 k第一个问题,用空格分隔。

输出

打印 Q 行。上 k第行,打印答案 k第题,即区间内完全包含的连续子区间的个数 [L_k, R_k] 形成稳定的排列。


示例输入 1

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

示例输出 1

11
4
6
3

示例输入 2

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

示例输出 2

6
1
4
2

示例输入 3

12 8
4 7 3 3 8 2 6 6 1 5 9 4
1 12
1 6
3 8
5 11
7 12
2 2
4 10
9 12

示例输出 3

23
10
12
13
11
1
12
8

示例输入 4

30 12
15 3 8 8 20 1 2 2 2 25 10 10 5 30 4 6 6 12 11 40 7 7 7 50 9 18 18 17 60 1
1 30
1 15
16 30
5 20
10 25
2 9
12 18
21 29
6 6
14 24
3 27
28 30

示例输出 4

192
53
68
81
55
20
14
36
1
42
160
4

示例输入 5

1 1
1000000000
1 1

示例输出 5

1