自动搬运

查看原文

来自洛谷，原作者为

	continueOI Always continue; Never break;梦想变成一只软趴趴的小猫||AFO？

搬运于2025-08-24 21:14:17，当前版本为作者最后更新于2022-12-03 20:15:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目描述

给定一个长度为 $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;
}