题面

题面描述

给定一个长度为$n$的序列$a_{1∼n}$。

$q$次询问，每次给出一个区间$[l,r]$，要求找出$[l,r]$的一个子区间$[l′,r′]$，满足它不包含$[l,r]$中所有种类的数，且它的长度$r′−l′+1$最大。你只需输出这个最大长度。

特别提醒，$[l′,r′]$可以是长度为$0$的空区间。

输入格式

第一行一个正整数$n$。

接下来一行$n$个正整数$a_{1∼n}$。

随后一行一个正整数$q$。

接下来$q$行，每行两个正整数$l,r$表示一个询问区间。

输出格式

共$q$行，每行一个整数表示答案。

样例一

input

5
1 3 2 3 4
4
2 4
1 3
2 5
1 1

output

1
2
3
0

数据范围与约定

Subtask1(20%)：$n,q≤100$

Subtask2(20%)：$n≤10^3$

Subtask3(20%)：保证数据随机

Subtask4(20%)：$n≤2×10^5$

Subtask5(20%)：无特殊限制

对于100%的数据，$1≤n,q,a_i≤2×10^6$

题解

分别考虑不选择某种数的情况，则要么选择它在这个区间内相邻两次出现之间的部分，要么选择左端点到它在这个
区间内首次出现的部分，要么选择它在这个区间内最后出现到右端点的部分。
我们离线处理这个问题。事先预处理出$pre_i,nxt_i$ 表示与$a_i$相同的元素上一次/下一次出现的位置。
对于相邻两次出现，可以用$i-pre_i-1$计算，枚举右端点求$i<=r$的贡献，要求满足$pre_i>=l$ ，直接以$pre_i$为下标
用树状数组维护即可。
对于首次出现，同样枚举右端点求$i<=r$的贡献，要求满足$pre_i<l$，以$pre_i$为下标用树状数组维护出$i$的最大值。
对于最后出现只要枚举左端点，也是类似的处理。

我的话没有处理$nxt$，把数组翻转以后对$l,r$处理了一下然后清空前后缀最大值树状数组（注意从$1$开始，所以下标要加$1$）然后再做了一遍求最大值。

代码

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Maxn 2000005
#define lowbit(x) (x&(-x))
using namespace std;
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=='\n'||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;
struct que{int l,r,id,ans;}t[Maxn];
int q,n,a[Maxn],wz[Maxn],pre[Maxn],c1[Maxn],c2[Maxn];
inline bool cmp1(que a,que b){return a.r<b.r;}
inline bool cmp2(que a,que b){return a.id<b.id;}
inline void add1(int i,int x){i++;while (i<=n+1) c1[i]=max(c1[i],x),i+=lowbit(i);}
inline int get1(int i){int res=0;i++;while (i) res=max(res,c1[i]),i-=lowbit(i);return res;}
inline void add2(int i,int x){i++;while (i<=n+1) c2[i]=max(c2[i],x),i+=lowbit(i);}
inline int get2(int i){i++;int res=0;while (i) res=max(res,c2[i]),i-=lowbit(i);return res;}
int main()
{
	freopen("dusk2.in","r",stdin);
	freopen("dusk.out","w",stdout);
	fin>>n;for (int i=1;i<=n;i++) fin>>a[i],pre[i]=wz[a[i]],wz[a[i]]=i;
	fin>>q;for (int i=1;i<=q;i++) fin>>t[i].l>>t[i].r,t[i].id=i;
	sort(t+1,t+q+1,cmp1);
	int x=1;
	for (int i=1;i<=q;i++)
	{
		while (x<=t[i].r) add1(pre[x],x),add2(n-pre[x],x-pre[x]-1),x++;
		t[i].ans=max(t[i].ans,get1(t[i].l-1)-t[i].l);
		t[i].ans=max(t[i].ans,get2(n-t[i].l));
	}
	memset(wz,0,sizeof(wz));
	memset(pre,0,sizeof(pre));
	memset(c1,0,sizeof(c1));
	memset(c2,0,sizeof(c2));
	reverse(a+1,a+n+1);
	for (int i=1;i<=n;i++) pre[i]=wz[a[i]],wz[a[i]]=i;
	for (int i=1;i<=q;i++) t[i].l=n-t[i].l+1,t[i].r=n-t[i].r+1,swap(t[i].l,t[i].r);
	sort(t+1,t+q+1,cmp1);
	x=1;
	for (int i=1;i<=q;i++)
	{
		while (x<=t[i].r) add1(pre[x],x),add2(n-pre[x],x-pre[x]-1),x++;
		t[i].ans=max(t[i].ans,get1(t[i].l-1)-t[i].l);
		t[i].ans=max(t[i].ans,get2(n-t[i].l));
	}
	sort(t+1,t+q+1,cmp2);
	for (int i=1;i<=q;i++) fout<<t[i].ans<<'\n';
	return 0;
}