题目
A 是某公司的 CEO，每个月都会有员工把公司的盈利数据送给 A，A 是个与众不同的怪人，A 不注重盈利还是亏本，而是喜欢研究「完美序列」：一段连续的序列满足序列中的数互不相同。 A 想知道区间 [L,R] 之间最长的完美序列长度。
尝试
一开始想的是用权值线段树，这样只要满足min[l,r]=1那么这段就是合法的。 又想了想让每个合法区间对提问更新，并不太可行。
题解
ST表+二分 绕了一大圈，其实应该直接求以i为结尾的最大长度... 设其为f[i]，为了方便递推，再设一个st[i]表示以i结尾的最大长度的开头，那么有。 st[i]的转移有两条限制：一是显然不能比st[i-1]还前（小），二是不能到最近一次出现的a[i]（a[i]为盈利价值）。用last[i]维护数字i最近的位置，所以。
考虑求答案吧，一段区间[ql,qr]，那么最优解的右端点一定在[ql,qr]之间。左端点呢，随意对吧，没有什么要求。但还是有一点特别的，对于一个k，如果st[k]<ql而且st[k-1]<ql，那么k一定比k-1优秀。 所以答案的来源只有两种可能了，一是一个最大的k满足st[k]<ql，二是从k+1（根据上面k的特点，有st[k+1]>=ql）开始一直到r，f的最大值，即。 那么对于那段区间最大值，用ST表维护就好了。k的值因为st递增，所以二分可以得到。 还要注意一下k的细节，如果st[r]<l要特判一下，此时k会超出[l,r]的范围。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10,MAXA=1e6;
int bin[20],log[MAXN];
void pre_work()
{
for(int i=0;i<=20;i++) bin[i]=1<<i;
log[0]=-1;for(int i=1;i<MAXN;i++) log[i]=log[i>>1]+1;
}
int n,m;
int st[MAXN];
int last[MAXA*2+10];
int f[MAXN][20];
int query(int l,int r)
{
int s=log[r-l+1];
return max(f[l][s],f[r-bin[s]+1][s]);
}
int main()
{
pre_work();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int x;scanf("%d",&x);x+=MAXA;
st[i]=max(st[i-1],last[x]+1);
f[i][0]=i-st[i]+1;//debug f[i][0]=st[i]
last[x]=i;
}
for(int i=1;i<=19;i++)
for(int j=1;j+bin[i]-1<=n;j++) f[j][i]=max(f[j][i-1],f[j+bin[i-1]][i-1]);//debug j<=n
while(m--)
{
int l,r,k;
scanf("%d%d",&l,&r);l++,r++;
if(st[r]<l) k=r+1;
else k=lower_bound(st+1,st+n+1,l)-st;
int ans=0;
if(k>l) ans=k-l;
if(k<=r) ans=max(ans,query(k,r));
printf("%d\n",ans);
}
return 0;
}
