BZOJ-4149: [AMPPZ2014]Global Warming

Description

给定一个序列a[1],a[2],...,a[n]。请从中选出一段连续子序列，使得该区间最小值唯一、最大值也唯一。输出选出的子序列的长度的最大值以及取到最大值时左端点的最小值。n<=5*10^5

题解：CQzhangyu的blog：【BZOJ4149】[AMPPZ2014]Global Warming 单调栈+RMQ+二分
难点在于发现性质：对于最大值为x的可行区间，其长度最大区间的最小值一定为整个区间的最小值。
证明：反证，假如不含有最小值mi，那么将l或r拓展到mi的位置所对应的区间也是合法且长度优于原区间的。

#include <cstdio>
#include <vector>
#include <cctype>
#include <cstring>
#include <algorithm>
#define N 501000 
#define pb push_back 
using namespace std;
inline char nc()
{
    static char buf[10000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,10000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int re=0; char fl=0,ch=nc();
    while(!isdigit(ch)) fl|=(ch=='-'),ch=nc();
    while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
    return fl ? -re : re;
}
int n,a[N],b[N],c[N],tot;
int z[N],top,L[N],R[N],mi[N][19],Log[N],ans1,ans2;
vector<int>ve[N];
void getans(int l,int r)
{
    if(r-l+1>ans1) ans1=r-l+1,ans2=l;
    else if(r-l+1==ans1) ans2=min(ans2,l);
}
int main()
{
    n=read(); int i,j;
    for(i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
    for(i=1;i<=n;++i) b[i]=a[i]=read();
    sort(b+1,b+n+1);
    for(c[++tot]=b[1],i=2;i<=n;++i) if(b[i]!=b[i-1]) c[++tot]=b[i];
    for(i=1;i<=n;++i) mi[i][0]=a[i]=lower_bound(c+1,c+tot+1,a[i])-c,ve[a[i]].pb(i);
    for(i=1;i<=Log[n];++i)
        for(j=1;j+(1<<i)-1<=n;++j)
            mi[j][i]=min(mi[j][i-1],mi[j+(1<<(i-1))][i-1]);
    for(top=0,z[0]=0,i=1;i<=n;++i)
    {
        while(top&&a[z[top]]>a[i]) --top;
        L[i]=z[top]+1; z[++top]=i;
    }
    for(top=0,z[0]=n+1,i=n;i;--i)
    {
        while(top&&a[z[top]]>a[i]) --top;
        R[i]=z[top]-1; z[++top]=i;
    }
    for(top=0,z[0]=0,i=1;i<=n;++i)
    {
        while(top&&a[z[top]]<a[i]) --top;
        b[i]=z[top]+1; z[++top]=i;
    }
    int l,r,x,p,lo;
    for(top=0,z[0]=n+1,i=n;i;--i)
    {
        while(top&&a[z[top]]<a[i]) --top;
        l=b[i]; r=z[top]-1; lo=Log[r-l+1];
        x=min(mi[l][lo],mi[r-(1<<lo)+1][lo]);
        p=lower_bound(ve[x].begin(),ve[x].end(),i)-ve[x].begin();
        if(p<(int)ve[x].size()&&p>=0&&ve[x][p]>=l&&ve[x][p]<=r)
            getans(max(L[ve[x][p]],l),min(R[ve[x][p]],r));
        if(p-1<(int)ve[x].size()&&p-1>=0&&ve[x][p-1]>=l&&ve[x][p-1]<=r)
            getans(max(L[ve[x][p-1]],l),min(R[ve[x][p-1]],r));
        z[++top]=i;
    }
    printf("%d %d\n",ans1,ans2);
    return 0;
}