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