书店 - Problem

你拥有一家非常奇特的书店，店里出售旧书，但你把它们全部存放在一个书架上，顺序是随机的，而且你并不关心书的内容。你的顾客也不关心——他们走进店里，通常只是要求“书架上从这一本开始到那一本结束的所有书”。准确地说，每位顾客都会购买书架上某一段连续的（且非空的）书。

有时，你会遇到更挑剔的顾客，他们对书有更高的要求——实际上，他们希望书的大小合适。一位挑剔的顾客想要书架上的一个片段，其中所有书的高度都不小于 $l$ 且不大于 $h$。

给定一个整数序列——书架上所有书的高度——确定满足这些要求的连续片段的数量。

此外，我们提到书的顺序是随机的。形式上，输入序列是使用以下程序生成的，其中 $N \in \{1, 2, \dots, 100\,000\}$ 且 $M = 10^q$，其中 $q \in \{1, 2, \dots, 6\}$。

srand48(N + M);
for (int i = 0; i < N; ++i)
a[i] = 1 + lrand48() % M;

你实际上不需要知道 RAND48 库是如何工作的。只需假设函数 lrand48 返回均匀随机选取的 31 位非负整数即可。

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 5$)。接下来是各个测试用例，每个测试用例的格式如下：

测试用例的第一行包含书的数量 $n$ 和挑剔的顾客数量 $k$ ($1 \le n \le 200\,000, 1 \le k \le 500\,000$)。

第二行包含一个由 $n$ 个不超过 $1\,000\,000$ 的正整数组成的序列，表示从第一本（最左侧）到最后一本（最右侧）所有书的高度。

最后的 $k$ 行描述了顾客的要求。这 $k$ 行中的第 $i$ 行包含两个整数 $l_i, h_i$ ($1 \le l_i \le h_i \le 1\,000\,000$)，描述了一位要求书的高度不小于 $l_i$ 且不大于 $h_i$ 的顾客。

所有测试用例中书的总数不超过 $600\,000$，所有测试用例中顾客的总数不超过 $1\,500\,000$。

对于每位顾客，输出满足其要求的书序列中非空连续片段的数量。

2
10 3
9 9 3 2 1 9 6 9 1 7
1 13
6 6
2 9
5 1
66575 45720 67904 18764 35162
20000 80000

QOJ.ac