一、题目大意

本题中，给出一个长度为\(n\)的正整数数组，对每一个正整数 \(i\)，\(0 \leq i < n\)，给出一个正整数\(m_i\)，查询数组在下标\([i-m_i,i)\)范围内元素的最大值，记为\(M_i\)。给出\(T\)组询问，每组询问给出两个正整数\(p,q(0 \leq p < q)\)，分别询问满足有多少个\(M_i\)在区间\([0,p)\)和区间\([p,q)\)中。

其中

二、算法分析

为了解决问题，首先要求出每个区间的最大值。若对于每个区间，遍历区间中查询最大值，则时间复杂度为\(O(n^2)\)，在本题的数据范围下会造成超时。注意到这\(n\)个区间的左右端点序列都是单调不降的序列，于是考虑使用单调队列。

我们使用单调队列维护这个区间中的所有后缀最大值。当区间发生变化时，有如下操作：
（1）当区间的左端点向右移动时，若原来区间的某个后缀最大值在修改后的区间内，则该后缀最大值仍为修改后区间的某个后缀最大值；否则将该后缀最大值从区间中删去。因此，此时不断弹出队列头部的元素，直到队列第一个元素在修改后的区间内。
（2）当区间的右端点向右移动时，会向队列中新加入一个元素。设新加入的元素为\(a\)，若队列中存在一个元素\(b < a\)，则与队列中维护后缀最大值矛盾，需要将\(b\)从队列中删去。因此，此时不断弹出队列尾部的元素，直到队列中的最后一个元素大于等于\(x\)，此时\(x\)也是一个后缀最大值，则将\(x\)加入队列中。

经过以上操作，我们就可以正确维护当前区间内的所有后缀最大值。我们考虑这些后缀最大值中最靠前的一个，也即队列的首元素，设为\(m\)，显然\(m\)前面不可能存在比它更大的数，否则这些更大的数中会产生一个比\(m\)更靠前的后缀最大值，这与\(x\)为最靠前的后缀最大值矛盾。又因为\(m\)后面不会有比它更大的数，则\(m\)就是当前区间的最大值。

通过单调队列求出所有的\(M_i\)之后，可以将所有的\(M_i\)放入数组中，快速排序后，对于每次询问的\(p\)与\(q\)值采用二分查找，即可高效求出满足题设条件的\(M_i\)的个数。

三、代码实现

为了模拟区间的变化，我们用一个整型变量head来表示左端点，tail表示右端点，则区间的移动可以反映为head和tail的增减。在实现过程中，为了方便比较队列中元素与区间端点之间的位置关系，我们定义一个数组max_number_pos来存储所有后缀最大值在数组中的下标。则上述区间变化时对单调队列的操作如下： 

while(head != tail && max_number_pos[head] < i - search_day) {
    head ++;
}
max_number[i] = people_number[max_number_pos[head]];
while(head != tail && people_number[max_number_pos[tail - 1]] <= people_number[i]) {
    tail --;
}
max_number_pos[tail++] = i;

其中max_number[i] = people_number[max_number_pos[head]];一行表示获取队列中第一个后缀最大值下标对应的值，并将值存放在max_number数组中。

将所有的区间最大值都获取之后，将这个数组利用快速排序从小到大排序，然后进行二分查找，实现代码如下： 

int binary_search(int num[], int size, long long x) {
    int low = 0;
    int high = size;
    while(low < high) {
        int mid = (low + high) / 2;
        if(num[mid + 1] < x) {
            low = mid + 1;
        }
        else {
            high = mid;
        }
    }
    return low;
}

这样便可以直接得到num数组中小于x的元素个数。此后直接调用二分查找函数： 

int ans1 = binary_search(max_number, n, p);
int ans2 = binary_search(max_number, n, q);
cout<<ans1<<" "<<ans2-ans1<<'\n';

即可得到正确答案。

四、实现中值得注意的细节

  1. 在对数组进行排序的时候，我一开始是手写了一个快速排序函数，但是由于在手动实现中每次用于比较的基准数选取了区间中的第一个数，很容易被特殊数据导致复杂度退化，因此提交时出现了Time Limit Error的错误。于是考虑使用cstdlib库中自带的qsort()函数进行排序，通过手写排序函数：

    int cmp(const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

    则可以通过qsort(max_number + 1, n, sizeof(int), cmp);一行直接对数组进行排序。

  2. 注意到题目中的数据范围，在实现过程中，表示\(m_i,p,q\)的变量都需要设置为long long类型。相应地，二分查找函数参数中的x也应该传入long long类型。

五、时间与空间复杂度分析

  1. 时间复杂度分析：在本程序中，对单调队列进行操作时，左右端点至多进行\(n\)次移动，此部分复杂度为\(O(n)\)。对数组进行排序的复杂度为\(O(n\log{n})\)。每次查询进行二分查找的复杂度为\(O(\log{n})\)。则总时间复杂度为\(O((n+T)\log{n})\)。

  2. 空间复杂度分析：在本程序中，主要的空间开销在于存储初始数组、每个区间的最大值的下标、每个区间的最大值，则总空间复杂度为\(O(n)\)。