题目大意 ：给你一个整数序列，定义一个合法子串为子串内所有数互不相同，会有很多询问，求区间$[L,R]$内最长连续合法子串长度
一道思维不错的$RMQ$题，NOIP要是考这种题可能会考挂一片
预处理出$f_{i}$数组表示以i结尾的最长子串的起始位置，需要一个辅助$last$数组，表示某个数上一次出现的位置
那么$f_{i}=max(f_{i-1},last[a_{i}]+1)$
再$RMQ$预处理出区间内任意一个点结尾的最长子串长度
对于一个询问$[L,R]$，并不能直接用$RMQ$求出答案，因为有一些在$[L,R]$结尾的最长子串的起始位置可能超出$L$
然后发现$f_{i}$数组是递增的，所以对于一个询问，二分出一个位置，这个位置结尾的最长子串的左端点，是最后一个左端点超出$L$的位置
显然，答案要么是二分出的位置$k$到$L$的距离，或者是在$k+1$到$R$之间结尾的最长子串长度
时间$O(nlogn+mlogn)$
1 #include <vector> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define N 200010 6 #define M 2001000 7 #define maxn 1000000 8 #define inf 0x3f3f3f3f 9 using namespace std; 10 11 int n,m; 12 int gint() 13 { 14 int ret=0,fh=1;char c=getchar(); 15 while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();} 16 while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();} 17 return ret*fh; 18 } 19 20 int a[N],ma[N][20],la[M],f[N],lg[N]; 21 int query(int x,int y){ 22 if(x>y) return 0; 23 int len=y-x+1; 24 return max(ma[x][lg[len]],ma[y-(1<<lg[len])+1][lg[len]]); 25 } 26 27 int main() 28 { 29 scanf("%d%d",&n,&m); 30 for(int i=1;i<=n;i++) 31 scanf("%d",&a[i]); 32 lg[1]=0; 33 for(int i=2;i<=n;i++) 34 lg[i]=lg[i>>1]+1; 35 for(int i=1;i<=n;i++) 36 if(!la[a[i]+maxn]){ 37 f[i]=max(f[i-1],1); 38 la[a[i]+maxn]=i; 39 }else{ 40 f[i]=max(f[i-1],la[a[i]+maxn]+1); 41 la[a[i]+maxn]=i; 42 } 43 for(int i=1;i<=n;i++) ma[i][0]=i-f[i]+1; 44 for(int j=1;j<=lg[n];j++) 45 for(int i=1;i+(1<<j)-1<=n;i++) 46 ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]); 47 int x,y; 48 for(int i=1;i<=m;i++) 49 { 50 scanf("%d%d",&x,&y); 51 x++,y++; 52 int l=x,r=y,ans=x; 53 while(l<=r){ 54 int mid=(l+r)>>1; 55 if(f[mid]<x) ans=mid,l=mid+1; 56 else r=mid-1; 57 } 58 printf("%d ",max(ans-x+1,query(ans+1,y))); 59 } 60 return 0; 61 }