#D. 向流星许愿(star)

    Type: Default File IO: star 15000ms 128MiB

向流星许愿(star)

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

巡有一个长度为 nn 的数组 a1,a2,,ana_1,a_2,\dots,a_n。如果对一个三元对 (i,j,k)(i,j,k) 满足:

  • i<j<ki<j<k
  • ai=ak>aja_i=a_k>a_j

那么巡称这种三元对为流星对。

巡有 qq 个询问,每次询问给定 l,rl,r。巡想要知道在 al,al+1,,ara_l,a_{l+1},\dots,a_r 之中有多少流星对。

巡会对流星许什么愿望呢?

image

输入格式

第一行两个正整数表示 n,qn,q

接下来一行 nn 个正整数表示 a1,a2,,ana_1,a_2,\dots,a_n

接下来 qq 行,每行两个正整数表示 l,rl,r

输出格式

qq 行,每行一个非负整数表示答案。

样例 1

【样例输入】

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

【样例输出】

4
4
1
0
0

样例 2

见下发 star2.in/ans\textit{star2.in/ans}

该样例满足测试点 11 的性质。

样例 3

见下发 star3.in/ans\textit{star3.in/ans}

该测试点满足测试点 1111 的性质。

数据范围

对所有数据,满足 n,q106n,q\leq 10^61ain1\leq a_i\leq n

测试点编号 nn\leq qq\leq 特殊性质
11 100100
22 500500
33 50005000
474\sim 7 10610^6 aia_i[1,n][1,n] 之内随机生成
8108\sim 10 2×1052\times 10^5
111311\sim 13 5×1055\times 10^5
141514\sim 15 10610^6 10610^6 l=1l=1
161816\sim 18 1010
192019\sim 20 10610^6

NOIP 2024 模拟赛(三)

Not Attended
Status
Done
Rule
OI
Problem
4
Start at
2024-8-8 8:00
End at
2024-8-8 12:00
Duration
4 hour(s)
Host
Partic.
38