小Y的线段树¶
预估时间限制：1.5 秒。内存限制：512 MB。
实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(10\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
本题采用倍率十，为支持逐条回答询问的倍增实现保留至少两倍实测余量。各程序耗时见测量记录。
背景故事¶
“这是什么newbee操作？”
小Y不是死宅，他喜欢玩碧蓝，小学时还是体育生，所以他出了一道线段树题。
他有一个长度为 \(N\) 的序列。他会告诉你序列的长度和每个位置的元素，却说“不会给你这个序列”。接下来有 \(M\) 次询问：将区间 \([l,r]\) 中的元素从左到右依次放入一个初始为空的严格单调递减栈，最终栈的大小是多少？
形式化问题描述¶
给定长度为 \(N\) 的整数序列 \(a_1,\ldots,a_N\) 和 \(M\) 个询问。每个询问给出 \([l,r]\) ，独立从空栈开始，按 \(a_l,a_{l+1},\ldots,a_r\) 的顺序处理每个元素 \(v\) ：
- 只要栈非空且栈顶值不大于 \(v\) ，就弹出栈顶。
- 将 \(v\) 压入栈。
因此，栈中元素从底到顶严格递减，相等的旧元素也会弹出。输出每次询问处理结束后的栈大小。询问之间不保留栈，也不修改序列。
输入格式¶
第一行两个整数 \(N,M\) .第二行 \(N\) 个整数 \(a_1,\ldots,a_N\) .接下来 \(M\) 行，每行两个整数 \(l,r\) .
输出格式¶
输出 \(M\) 行，第 \(i\) 行一个整数，表示第 \(i\) 个询问的答案。
样例¶
样例 1¶
输入¶
5 4
5 3 3 4 2
1 5
2 4
2 3
5 5
输出¶
3
1
1
1
样例 2¶
输入¶
2 1
1 2
1 2
输出¶
1
样例 3¶
输入¶
3 2
9 7 5
1 3
2 3
输出¶
3
2
样例解释¶
第一组的四个最终栈从底到顶分别为 \((5,4,2)\) 、\((4)\) 、\((3)\) 、\((2)\) .相等的两个三只留下后读入的一个。第二组中新值二会弹出一。第三组两个区间本身都严格递减。
数据范围与保证¶
\(1\le N,M\le5\times10^5\) , \(0\le a_i\le10^9\) , \(1\le l\le r\le N\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |