题目大意
-
给定一个长度为 (n) 的序列
-
每次给出一个区间 ([l,r]) ，要求找出 ([l,r]) 的一个子区间 ([l',r']) ，满足它不包含 ([l,r]) 中所有种类的数，且它的长度 (r'−l'+1) 最大
问题求解
拿到这道题发现在线求解非常非常难，无从下手，而离线就很容易去思考
对于这个询问区间，答案只可以有三种，假设我们要不选一个数
-
从头到这个数第一次出现的位置
-
中间两次出现位置中间
-
最后一次出现到尾
我们先来处理第二种可能 （看似最简单）
先把询问区间按左端点排序，然后构造出一个数组(lst[i])表示这个数后面一次出现这个数的位置
然后从后往前刷，每次碰到一个数出现次数超过两次以后，就把 (lst[i]-j-1) 放到 $lst[j] $ 这个位置，对于一个区间 $(L,R) $ ，我们需要寻找 ((L,R)) 中最大的 (lst[i]-j-1)因为我们是倒序刷的，所以可以用树状数组来维护最大值
再来思考第一种情况，这次我们正这刷，因为我们要找第一次出现的，我们先把每个数第一次出现的位置放到 (i) 的位置上，求最大值同样也用树状数组来实现
然后每次 (L) 向右边推的时候，我们把这个数下一次出现的位置放到树状数组里面去，由于我们刷最大值，所以直接刷就好了
最后来考虑第三种情况，同理，我们只需要把串反过来就和第一种情况一样了
代码实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;
int N,M,a[maxn],vis[maxn],lst[maxn],nxt[maxn],c[maxn],Q,Ans[maxn];
struct qus{
int l,r,id;
bool operator <(const qus B)const {return l<B.l;}
}q[maxn];
struct IO{
static const int S=1<<21;
char buf[S],*p1,*p2;int st[105],Top;
~IO(){clear();}
inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='
'||x=='r');return *this;}
template<typename T>inline IO&operator >> (T&x){
x=0;bool f=0;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
f?x=-x:0;return *this;
}
inline IO&operator << (const char c){pc(c);return *this;}
template<typename T>inline IO&operator << (T x){
if(x<0) pc('-'),x=-x;
do{st[++st[0]]=x%10,x/=10;}while(x);
while(st[0]) pc('0'+st[st[0]--]);
return *this;
}
}fin,fout;
void add_x(int x,int data){
for(int i=x;i<=N;i+=i&-i) c[i]=max(c[i],data);
}
int get(int x){
int ret=0;
for(int i=x;i;i-=i&-i)ret=max(ret,c[i]);
return ret;
}
int main(){
fin>>N;
for(int i=1;i<=N;i++)fin>>a[i];
fin>>Q;
for(int i=1;i<=Q;i++)fin>>q[i].l>>q[i].r,q[i].id=i;
sort(q+1,q+1+Q);
for(int i=1;i<=N;i++)lst[a[i]]=N+1;
for(int i=Q,j=N;i;i--){
while(j&&j>=q[i].l){
(lst[a[j]]!=N+1)&&(add_x(lst[a[j]],lst[a[j]]-j-1),0);
lst[a[j]]=j;j--;
}
Ans[q[i].id]=max(Ans[q[i].id],get(q[i].r));
}
memset(c,0,sizeof c);
for(int i=1;i<=N;i++) lst[a[i]]=N+1;
for(int i=N;i;i--) nxt[i]=lst[a[i]],lst[a[i]]=i;
for(int i=1;i<=N;i++)if(!vis[a[i]]) add_x(i,i),vis[a[i]]=1;
for(int i=1,j=1;i<=Q;i++){
while(j<=N&&j<q[i].l) add_x(nxt[j],nxt[j]),j++;
Ans[q[i].id]=max(Ans[q[i].id],get(q[i].r)-q[i].l);
}
memset(c,0,sizeof c);
memset(vis,0,sizeof vis);
reverse(a+1,a+1+N);
for(int i=1;i<=Q;i++)q[i].l=N-q[i].l+1,q[i].r=N-q[i].r+1,swap(q[i].l,q[i].r);
sort(q+1,q+1+Q);
for(int i=1;i<=N;i++) lst[a[i]]=N+1;
for(int i=N;i;i--) nxt[i]=lst[a[i]],lst[a[i]]=i;
for(int i=1;i<=N;i++)if(!vis[a[i]]) add_x(i,i),vis[a[i]]=1;
for(int i=1,j=1;i<=Q;i++){
while(j<=N&&j<q[i].l) add_x(nxt[j],nxt[j]),j++;
Ans[q[i].id]=max(Ans[q[i].id],get(q[i].r)-q[i].l);
}
for(int i=1;i<=Q;i++) fout<<Ans[i]<<'
';
return 0;
}