思路:

假设我们现在已经求出所有以\(i\)为区间起点的区间的答案.

那么如何求出所有以\(i+1\)为区间起点的区间的答案呢?呢?

考虑现在没有第\(i\)个数了.那么一些区间的答案就会减少.令区间终点为\(j\)的答案为\(f[j]\),在\(i\)后面第一个数值与\(i\)相同的位置为\(next[i]\),那么终点为\([i+1,next[i]-1]\)这段区间内的答案都应该对\(w[i]\)取一个min.

这个非常容易理解.

于是将询问排序,然后用一颗线段树维护标记就行了.时间复杂度\(O(n+m)logn\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 0x3f3f3f3f
 
namespace Fio{
    inline int getc(){
#ifndef ONLINE_JUDGE
        static const int L=1<<1;
#else
        static const int L=1<<15;
#endif
        static char buf[L],*readS=buf,*readT=buf;
        if(readS==readT){readT=(readS=buf)+fread(buf,1,L,stdin);if(readS==readT)return EOF;}
        return*readS++;
    }
    inline bool digit(char c){return c>='0'&&c<='9';}
    template<typename T>inline void Get(T&x){
        int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    char buf[1500010],*o=buf;
    template<typename T>inline void Print(T x){
        static int stk[100];int top=0;
        if(!x)*o++=48;else{for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++=stk[i]+48;}
        *o++='\n';
    }
    inline void final(){fwrite(buf,1,o-buf,stdout);}
}
 
#define N 200010
#define M 200010
int n,m,a[N];
 
struct Query{
    int l,r,lab;
    Query(){}
    Query(int _l,int _r):l(_l),r(_r){}
    bool operator<(const Query&B)const{return l<B.l;}
}Q[M];int res[N];
 
bool vis[N];
 
int ans[N];
struct Node{
    int l,r,c,ans;
}S[N<<2];int cnt;
int Build(int tl,int tr){
    int q=++cnt,mid=(tl+tr)>>1;
    S[q].c=-INF,S[q].ans=ans[mid];
    if(tl==tr)return q;
    S[q].l=Build(tl,mid),S[q].r=Build(mid+1,tr);return q;
}
void Covit(int q,int c){
    S[q].c=(S[q].c==-INF||c<S[q].c)?c:S[q].c,S[q].ans=min(S[q].ans,c);
}
void Push(int q){
    if(S[q].c!=-INF)Covit(S[q].l,S[q].c),Covit(S[q].r,S[q].c),S[q].c=-INF;
}
void Cover(int q,int tl,int tr,int dl,int dr,int c){
    if(dl>dr)return;
    Push(q);
    if(dl<=tl&&tr<=dr){Covit(q,c);return;}
    int mid=(tl+tr)>>1;
    if(dr<=mid)Cover(S[q].l,tl,mid,dl,dr,c);
    else if(dl>mid)Cover(S[q].r,mid+1,tr,dl,dr,c);
    else Cover(S[q].l,tl,mid,dl,mid,c),Cover(S[q].r,mid+1,tr,mid+1,dr,c);
}
int Query(int q,int tl,int tr,int ins){
    if(tl==tr)return S[q].ans;
    Push(q);
    int mid=(tl+tr)>>1;
    if(ins<=mid)return Query(S[q].l,tl,mid,ins);else return Query(S[q].r,mid+1,tr,ins);
}
 
int nxt[N],lst[N];
 
int main(){
    Fio::Get(n),Fio::Get(m);register int i,j;
    for(i=1;i<=n;++i)Fio::Get(a[i]);
    for(i=1;i<=m;++i)Fio::Get(Q[i].l),Fio::Get(Q[i].r),Q[i].lab=i;sort(Q+1,Q+m+1);
     
    int lans=0;
    for(i=1;i<=n;++i){vis[a[i]]=1;for(;vis[lans];++lans);ans[i]=lans;}
 
    for(i=n;i>=1;--i)nxt[i]=lst[a[i]],lst[a[i]]=i;
    for(i=1;i<=n;++i)if(!nxt[i])nxt[i]=n+1;
     
    Build(1,n);
    j=1;
    for(i=1;i<=n;++i){
        for(;j<=n&&Q[j].l==i;++j)res[Q[j].lab]=Query(1,1,n,Q[j].r);
        if(i<n)Cover(1,1,n,i+1,nxt[i]-1,a[i]);
    }
     
    for(i=1;i<=m;++i)Fio::Print(res[i]);
     
    return Fio::final(),0;
}

思路:

貌似存在\(O(n)\)的算法,不过由于我太弱只想到了\(O(nlogn)\).

现在很困就发代码了...有问题回复找我吧.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 1000010
struct SegmentTree{
    int a[2100000],M;
    inline void Init(int _siz){
        for(M=1;M<(_siz+2);M<<=1);
        memset(a,0xc0,sizeof a);
    }
    inline void upd(int x,int to){
        for(a[x+=M]=to,x>>=1;x;x>>=1)a[x]=max(a[x<<1],a[x<<1^1]);
    }
    inline int ask(int tl,int tr){
        int res=-1<<30;
        for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
            if(~tl&1)res=max(res,a[tl^1]);
            if(tr&1)res=max(res,a[tr^1]);
        }return res;
    }
}Seg;
 
int up[N];
 
namespace Fio{
    inline int getc(){
#ifndef ONLINE_JUDGE
        static const int L=1<<1;
#else
        static const int L=1<<15;
#endif
        static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}return*S++;
    }
    inline bool digit(char c){return c>='0'&&c<='9';}
    template<typename T>inline void Get(T&x){
        int c=0;while(!digit(c=getc())&&c!='-');bool sign=c=='-';x=sign?0:c-'0';
        while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';if(sign)x=-x;
    }
}
 
int main(){
    int n;Fio::Get(n);register int i,j;
    Seg.Init(n);
    int x;for(i=1;i<=n;++i)Fio::Get(x),Fio::Get(up[i]),Seg.upd(i,x);
     
    int nowmax=Seg.ask(1,1);
    int lans,ans;
    for(lans=2;lans<=n;++lans){
        if(nowmax>up[lans])break;
        nowmax=max(nowmax,Seg.ask(lans,lans));
    }ans=--lans;
     
    for(i=2;i<=n;++i){
        nowmax=Seg.ask(i,lans);
        for(++lans;lans<=n;++lans){
            if(nowmax>up[lans])break;
            nowmax=max(nowmax,Seg.ask(lans,lans));
        }--lans;
        ans=max(ans,lans-i+1);
    }
     
    printf("%d",ans);
     
    return 0;
}