天天看点

【GDOI2016模拟3.9】奇妙的数列

Description

给出一个长度为n的数列b,求另一个长度为n的数列a中的最大值。其中,ai=i-k+1,k是最小的满足对于k<=j<=i,bk<=bj<=bi。

n<=10^7

Solution

可以发现,对于每一个i,ai是在它左边且小于等于它,且大于等于左端点的数的个数。

那我们枚举左端点。很明显合法的i存在于一段连续的大于等于它的区间中。那么我们可以找出它的右端点,然后处理处每一个位置左边第一个比它大的数的位置,慢慢往回找,知道某一个能覆盖左端点为止。

可以证明这个算法的复杂度是O(N)的。(虽然我不会)

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 10000005
using namespace std;
int a[N],b[N],c[N],d[N],n,ans;
int read() {
    char ch;
    while (!isdigit(ch=getchar()));int o=ch-;
    while (isdigit(ch=getchar())) o=o*+ch-;
    return o;
}
int main() {
    n=read();a[]=;d[]=;
    fo(i,,n) {
        a[i]=read();
        while (a[d[d[]]]<=a[i]) d[]--;
        b[i]=d[d[]];d[++d[]]=i;
    }a[]=-;d[]=;
    fd(i,n,) {
        while (a[d[d[]]]>=a[i]) d[]--;
        c[i]=d[d[]];if (!c[i]) c[i]=n+;d[++d[]]=i;
    }b[n+]=n;
    fo(i,,n) {
        int r=c[i]-;
        while (b[r]>i) r=b[r];
        ans=max(ans,r-i+);
    }
    printf("%d",ans);
}
           
下一篇: 父亲节