B3667题解

· · 题解

题目描述

给定一个长度为 n 的数列 a，对于其中每个长度为 k 的子区间，请你求出这个这个子区间构成的数列的所有后缀最大值的位置个数。

一个下标 i 是是数列 b 的后缀最大值下标当且仅当：对于所有的 i < j \leq |b|，都有 b_i > b_j，其中 |b| 表示 b 的元素个数。

解法

以样例为例先模拟一遍。

下面是文字说明：

很容易就可以想到，用暴力方法求解：每输入一个数，将其与之前的所有后缀最大值的数遍历，如果比它大，那么就将比它小的那个数删除，再判断队列最前面的数是不是第 l-k+1 个数即可。

利用双端队列这个数据结构，将当时的后缀最大值入队列，如果遍历后不是后缀最大值了，那么便出队列，每次操作判断是不是第 l-k+1 个数，若是，则将那个数出队列。便可以得到一下核心代码：

if(head-tail&&ans[tail+1]+k<=i) tail++; //尾出队 
while(head-tail&&stk[ans[head]]<=stk[i]) head--; //头出队 
ans[++head]=i; //头入队

这里解释一下，head-tail 指的是队列中剩余的元素数量，其余便不再多讲，详情请见我的这篇文章。

数据规模与约定

注意，由于对于全部的测试点，保证 1 \leq k \leq n \leq 10^6，1 \leq x_i \lt 2^{64}，所以需要开 unsigned long long。

关于时间复杂度

显然，每个元素至多只会进入队列中一次，也至多只会出一次，所以时间复杂度为 O(n)。因为共有 n 个数，所以单次输入比较输出结果的时间复杂度均摊大概是 O(1) 的。

代码（STL）：

#include<bits/stdc++.h>
using namespace std;
int n,k;
deque<int> ans;
array<unsigned long long,1000005> stk;
int main() {
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>stk.at(i);
        if(ans.size()&&ans.front()+k-1<i) ans.pop_front();
        while(ans.size()&&(stk.at(i)>=stk.at(ans.back())))
            ans.pop_back();
        ans.push_back(i);
        if(i>=k) cout<<ans.size()<<'\n';
    }
    return 0;
}

代码（用数组模拟）：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k,tail,head,ans[N];
unsigned long long stk[N];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) {
        scanf("%llu",stk+i);
        if(head-tail&&ans[tail+1]+k<=i) tail++;
        while(head-tail&&stk[ans[head]]<=stk[i]) head--; 
        ans[++head]=i;
        if(i>=k) printf("%d\n",head-tail);
    }
    return 0;
}