提高：RMQ问题:【例 3】与众不同
时间限制 : 1 秒
内存限制 : 512 MB
A 是某公司的 CEO，每个月都会有员工把公司的盈利数据送给 A，A 是个与众不同的怪人，A 不注重盈利还是亏本，而是喜欢研究「完美序列」：一段连续的序列满足序列中的数互不相同。
A 想知道区间 [L,R] 之间最长的完美序列长度。
输入
第一行两个整数 N,M，N 表示连续 N 个月，编号为 0 到 N−1，M 表示询问的次数；
第二行 N 个整数，第 i 个数表示该公司第 i 个月的盈利值 aii ；
接下来 M 行每行两个整数 L,R，表示 A 询问的区间。
输出
输出 M 行，每行一个整数对应询问区间内的完美序列的最长长度。
样例
输入
9 2 2 5 4 1 2 3 6 2 4 0 8 2 6
输出
6 5
提示
数据范围与提示：
对于全部数据，1≤N,M≤2×10^5,0≤L≤R≤N−1,∣ai∣≤10^6。
详细注释版代码：
/*
1.先处理每个位置的最长不重复子序列的长度
2.RMQ是从i位置向右跳2^j
假设以len[i]为i结尾的最长不重复子序列的长度
结尾是i，长度是len[i],起点是i-len[i]+1
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+2;
int a[N],len[N],dp[N][20],n,m,l,r;
unordered_map<int,int> lastpos;
int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;i++) scanf("%d",&a[i]);int l=0;for(int r=0;r<n;r++){//如果当前元素出现过，且最后一次出现的位置在窗口内 if(lastpos.count(a[r])){//l=前面出现过的a[r]这个数字的后面的+1位置//由于lastpos是全局保存的所以可能有a[r]这个数字出现在l之前 //所以需要max l=max(l,lastpos[a[r]]+1); }len[r]=r-l+1;//当前窗口的长度 lastpos[a[r]]=r;//更新当前元素的最新位置 }//RMQfor(int i=0;i<n;i++) dp[i][0]=len[i];for(int j=1;j<18;j++)for(int i=0;i+(1<<j)-1<n;i++)dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);while(m--){int a,b;scanf("%d%d",&a,&b);//二分int low=1,high=b-a+1,ans=0;while(low<=high){int mid=(low+high)/2;//计算对应子数组的结束位置//找长度为mid的子数组，其结束位置为l+mid-1;int endpos=a+mid-1;if(endpos>b){high=mid-1;continue;}//查询在[endpos,r]区间内是否存在len[r]>=mid的子数组//如果满足len[r]>mid,则确保子数组的左端点的左端一定在区间内 int maxx;if(endpos>b) maxx=0;else{int j=__lg(b-endpos+1);maxx=max(dp[endpos][j],dp[b-(1<<j)+1][j]);}if(maxx>=mid){//寻找更长的 ans=mid;low=mid+1;}else high=mid-1;}printf("%d\n",ans);}return 0;
}无注释版代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+2;
int a[N],len[N],dp[N][20],n,m,l,r;
unordered_map<int,int> lastpos;
int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;i++) scanf("%d",&a[i]);int l=0;for(int r=0;r<n;r++){if(lastpos.count(a[r])) l=max(l,lastpos[a[r]]+1);len[r]=r-l+1;lastpos[a[r]]=r;}for(int i=0;i<n;i++) dp[i][0]=len[i];for(int j=1;j<18;j++)for(int i=0;i+(1<<j)-1<n;i++)dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);while(m--){int a,b;scanf("%d%d",&a,&b);int low=1,high=b-a+1,ans=0;while(low<=high){int mid=(low+high)/2;int endpos=a+mid-1;if(endpos>b){high=mid-1;continue;}int maxx;if(endpos>b) maxx=0;else{int j=__lg(b-endpos+1);maxx=max(dp[endpos][j],dp[b-(1<<j)+1][j]);}if(maxx>=mid){ans=mid;low=mid+1;}else high=mid-1;}printf("%d\n",ans);}return 0;
}