思路:
假设我们现在已经求出所有以\(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;
}
