LOJ #10121 与众不同 (RMQ+二分)

题目大意：给你一个整数序列，定义一个合法子串为子串内所有数互不相同，会有很多询问，求区间$[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)$

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N 200010

 #define M 2001000

 #define maxn 1000000

 #define inf 0x3f3f3f3f

 using namespace std;

 int n,m;

 int gint()

 {

     int ret=,fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 int a[N],ma[N][],la[M],f[N],lg[N];

 int query(int x,int y){

     if(x>y) return ;

     int len=y-x+;

     return max(ma[x][lg[len]],ma[y-(<<lg[len])+][lg[len]]);

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)

         scanf("%d",&a[i]);

     lg[]=;

     for(int i=;i<=n;i++)

         lg[i]=lg[i>>]+;

     for(int i=;i<=n;i++)

         if(!la[a[i]+maxn]){

             f[i]=max(f[i-],);

             la[a[i]+maxn]=i;

         }else{

             f[i]=max(f[i-],la[a[i]+maxn]+);

             la[a[i]+maxn]=i;

         }

     for(int i=;i<=n;i++) ma[i][]=i-f[i]+;

     for(int j=;j<=lg[n];j++)

         for(int i=;i+(<<j)-<=n;i++)

         ma[i][j]=max(ma[i][j-],ma[i+(<<(j-))][j-]);

     int x,y;

     for(int i=;i<=m;i++)

     {

         scanf("%d%d",&x,&y);

         x++,y++;

         int l=x,r=y,ans=x;

         while(l<=r){

             int mid=(l+r)>>;

             if(f[mid]<x) ans=mid,l=mid+;

             else r=mid-;

         }

         printf("%d\n",max(ans-x+,query(ans+,y)));

     }

     return ;

 }

巴特西

LOJ #10121 与众不同 (RMQ+二分)

最新文章

热门文章