题解 | #与众不同#

离散化 + dp + ST 表

参考楼上大佬的题解，总结出下面的思路

r[i]：以 i 作为左端点时，其右端点的位置. 则以 i 为起点时，目标序列的最大长度为 r[i] - i + 1
r[i] 具有非减性质，这为二分提供了前提条件

对于区间[L,R]，求其内部最长"好序列"的长度时，区间内每个点都有可能是“最长好序列”的左端点
所以有两种情况：(1)存在 r[i] > R 的左端点  (2)不存在 r[i] > R 的左端点

对于(1)：
r[i] 大于 R 的左端点中，我们只需要考虑它们中最左边的那个(考虑r[i]的非减性,可用二分)，得到 ans1
r[i] <= R 的左端点中，只有 r[i] - i + 1 最大的是我们需要的(预处理好，用ST来找) ，得到 ans2
答案为 max(ans1,ans2)

对于(2):
只有 r[i] <= R 的左端点，我们用 ST 表 求出它们中 r[i] - i + 1 最大的，即是答案

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+10;

vector<int>V;
int log_2[N];
int f[N][20];
int a[N],r[N],cnt[N];
int n,m;

void ST(){
    log_2[1]=0;
    log_2[2]=1;
    for(int i=3;i<=n;i++) log_2[i]=log_2[i/2]+1;

    int k=log_2[n];
    for(int j=1;j<=k;j++)
      for(int i=1;i-1+(1<<j)<=n;i++)
         f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}

int query(int l,int rr){
    int k=log_2[rr-l+1];
    int x=rr+1-(1<<k);
    return max(f[l][k],f[x][k]);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],V.push_back(a[i]);
    sort(V.begin(),V.end());
    V.erase(unique(V.begin(),V.end()),V.end());
    for(int i=1;i<=n;i++) a[i]=lower_bound(V.begin(),V.end(),a[i])-V.begin()+1;

    for(int i=1,j=1;i<=n;i++){
        while(j<=n&&cnt[a[j]]<1) {
            cnt[a[j]]++;  // cnt数组下标:a[j] 可能为负数，所以提前离散化搞一下数组a
            j++;
        }
        r[i]=j-1;
        cnt[a[i]]--;
    }

    for(int i=1;i<=n;i++) f[i][0]=r[i]-i+1;
    ST();

    int L,R;
    while(m--){
        cin>>L>>R;
        L++,R++;
        int ans=0;
        int j=upper_bound(r+L,r+R+1,R)-r;
        if(j<=R) {
            ans=R-j+1;
            if(j-1>=L) ans=max(ans,query(L,j-1));
        }
        else ans=query(L,R);
        cout<<ans<<endl;
    }
    return 0;
}