10121. 「一本通 4.2 例 3」与众不同
题意
定义完美序列：一段连续的序列满足序列中的数互不相同。 想知道区间 [L,R] 之间最长的完美序列长度。
思路
个数结尾的最长完美序列的起始位置。
设个数结尾的最长完美序列的长度
由
- 左边一部分的st值不在区间内，即<l_i
- 右边一部分的st值不在区间内，即ge l_i
_i，可得：
那么整个区间
- 左边：很显然为mid_i-l_i
- 右边：MAX(m_i…r_i)
所以右边的长度要使用ST表，即RMQ来求。 整个问题的时间复杂度：
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cstring>
#include<cmath>
#define ll long long
const int N=2e5 5,M=1e6;
using namespace std;
inline ll read(){
char ch=getchar();ll res=0,f=1;
while(ch<'0'ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=res*10 ch-'0',ch=getchar();
return res*f;
}
inline void write(ll zx){
if(zx<0) zx=-zx,putchar('-');
if(zx<10) putchar(zx '0');
else{
write(zx/10);
putchar(zx '0');
}
}
ll n,m,f[N][20],st[N],las[M<<1];
void ST(){
for(ll j=1;(1<<j)<=n;j ){
for(ll i=1;i (1<<j)-1<=n;i ){
f[i][j]=max(f[i][j-1],f[i (1<<(j-1))][j-1]);
}
}
}
ll RMQ(ll l,ll r){
ll k=0;
while((1<<(k 1))<=r-l 1) k ;
return max(f[l][k],f[r-(1<<k) 1][k]);
}
ll find(ll l,ll r){
if(st[l]==l) return l;
if(st[r]<l) return r 1;
int L=l,R=r;
while(L<=R){
int m=L R>>1;
if(st[m]<l) L=m 1;
else R=m-1;
}
return L;
}
int main(){
n=read();m=read();
for(ll i=1;i<=n;i ){
int x=read();
st[i]=max(st[i-1],las[x M] 1);
f[i][0]=i-st[i] 1;
las[x M]=i;
}
ST();
for(ll i=1;i<=m;i ){
ll L,R;
L=read();R=read();L ;R ;
ll mid=find(L,R),ans=0,tmp;
if(mid>L) ans=mid-L;
if(mid<=R){
tmp=RMQ(mid,R);
ans=max(ans,tmp);
}
write(ans);putchar('n');
}
return 0;
}
