luogu3512-POI

发表于 | 分类于

可能我太弱了吧，这么水的题做了半天qwq。。。。

关于数据范围n<=3000000我们可以联想到这大概是一道O(n)做法的题，然而我也就只想到了这儿，查题解发现开两个单调队列扫过去就好了。

易得这道题所求的子序列l是单增的，所以我们开两个单调队列，一个单增一个单减，分别维护l到当前的最小和最大值，并且在不合法时将l右挪。每读进一个数，我们就把它和队尾比较一下，拿单增序列为例，若当前队尾的数大于新读入的，就把队尾弹出，直到队尾小于当前值；单减则反之。这样，两个队头就记录了l到当前位置的最值。将它们做差，判断是否合法，若不合法则弹出两个队首中对应l更靠前的并更新l，得到i-l+1即为当前答案，比较更新即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//代码参考黄学长
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int qn[3000006];
int qx[3000006];
int a[3000006];
int ns=1,ne,xs=1,xe;
int ans;
int main()
{
    int n,k;
    scanf("%d%d",&k,&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int t=1;
    for(int i=1;i<=n;i++)
    {
        while(ne>=ns&&a[i]<=a[qn[ne]])ne--;
        while(xe>=xs&&a[i]>=a[qx[xe]])xe--;
        qn[++ne]=i;
        qx[++xe]=i;
        while(a[qx[xs]]-a[qn[ns]]>k)
            if(qx[xs]<qn[ns])t=qx[xs]+1,xs++;
            else t=qn[ns]+1,ns++;
        ans=max(ans,i-t+1);
    }
    printf("%d",ans);
    return 0;
}

今天才发现自己还不能分清哪儿是队首哪儿是队尾连题解都看不懂QAQ