一.题意

一道比较综合的RMQ（倍增）问题。
给你 (n) 个数 (a_1,a_2,...,a_n)，(m) 次询问，每次给定一个区间 ([l,r]) ，让你求出最长的一段序列，满足这个序列中的数各不相同，输出这段序列的长度。
对于全部数据，(1le N,Mle 2 imes 10^5) , (0le Lle Rle N-1) , (|a_i|le 10^6)

二.思路

• 首先我们令 (st[i]) 表示以 (i) 这个下标 结尾的最长完美序列的开始位置，(st[i]=max(st[i-1],lst[a[i]]+1))
• 我们令 (lst[i]) 表示 (i) 这个数最后一次出现的下标，(lst[i]=lst[a[i]])
• 我们令 (f[i]) 表示以 (i) 这个下标 结尾的最长完美序列的长度，(f[i]=i-st[i]+1)
• (st,lst,f) 都可以在 (O(n)) 的时间复杂度下完成

不难发现 (st) 是一个非降的序列，那么对于每一次 ([l,r]) 的区间询问中，(st) 的值可能出现两种情况

1. 左边的一部分 (st) 值不属于所求的区间内，即小于 (l)
2. 右边的一部分 (st) 的值一直大于等于 (l) ，由于 (st) 数组内元素具有单调性，所以我们不难想到用二分找出这个分界点 (mid)

经过上述的预处理后，则要求的 ([l,r]) 的完美序列长度可以分成两部分解决

1. 左边的最大长度即为 (mid-l+1)
2. 右边的最大长度即为 ([mid+1,r]) 这个区间内 (f) 数组的最大值

注意到，([mid+1,r]) 这个区间的最大值可以用 ST 表进行维护 （ST表不会的可以参考这里）

三.实现代码

这个代码的实现细节还挺多的

1. (a[i]) 的值可能是负数，会导致 (lst) 数组下标访问越界，所以我们需要将所有 (a[i]) 加上一个偏移值 (10^6)
2. (lst)数组存的是某个数在序列中最后一次出现的下标，所以数组要开到 (2 imes 10^6)
3. 要注意考虑二分查找中的边界问题

题目传送门 没想到这题竟然是青题
完整代码

#include<bits/stdc++.h>
using namespace std;
//#define int long long 
const int N=2e5+5;
const int M=1e6;
int n,q,a[N],lst[2*M+5],st[N],f[N],g[N][19],lg[N];
inline int ask(int l,int r){
	if (l>r)return 0;
	int p=lg[r-l+1];
	return max(g[l][p],g[r-(1<<p)+1][p]);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]+=M;
		st[i]=max(st[i-1],lst[a[i]]+1);
		lst[a[i]]=i;
		g[i][0]=f[i]=i-st[i]+1;
	}
	lg[2]=1;
	for(int i=3;i<=n;i++){
		lg[i]=lg[i/2]+1;
	}
	for(int j=1;j<=18;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			g[i][j]=max(g[i][j-1],g[i+(1<<(j-1))][j-1]);
		}
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		l++,r++;
		int left=l,right=r,wz=l;
		while(left<=right){
			int mid=(left+right)>>1;
			if (st[mid]<l){
				wz=mid;
				left=mid+1;
			}else{
				right=mid-1;
			}
		}
		int ans=max(wz-l+1,ask(wz+1,r));
		cout<<ans<<"
";
	}
	return 0;
}