线段树即可。

首先，定义$nxt[i]$为和$a[i]$相同的下一个数的位置，$lst[i]$为和$a[i]$相同的上一个数的位置。

从大到小枚举删数后的最长完美序列在原序列中的右端点$r$，同时用线段树维护每个位置$i$是否对不同数的个数有贡献（也就是$nxt[i]$是否大于$r$），不难发现$r$左移之后只有$lst[r]$变得有了贡献。在线段树上寻找一个$i$使得$rank(r)-rank(i)>k+1$且$i$最大，最后数一下$[i+1,r]$中满足$a[p]=a[r]$的$p$有多少个来更新答案。

时间复杂度$O(n \log n)$，空间复杂度$O(n)$。

Code

#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;
const int maxn=100001;
struct segtree{
    int sumv[maxn*4];
    int n;
    int kth(int k){
        int o=1,l=1,r=n;
        while(l<r){
            int mid=(l+r)/2;
            if(k<=sumv[o*2])
                o*=2,r=mid;
            else k-=sumv[o*2],o=o*2+1,l=mid+1;
        }
        return l;
    }
    int ql,qr;
    int query(int o,int l,int r){
            if (ql<=l && qr>=r)
                    return sumv[o];
            int mid=(l+r)/2;
            int ans=0;
            if (ql<=mid)
                    ans+=query(o*2,l,mid);
            if (qr>mid)
                    ans+=query(o*2+1,mid+1,r);
            return ans;
    }
    int rank(int x){
            ql=1,qr=x;
            return query(1,1,n);
    }
    int p,v;
    void add(int o,int l,int r){
        if (l==r){
            sumv[o]+=v;
            return;
        }
        int mid=(l+r)/2;
        if (p<=mid)
            add(o*2,l,mid);
        else add(o*2+1,mid+1,r);
        sumv[o]+=v;
    }
    void add(int p,int v){
        this->p=p;
        this->v=v;
        add(1,1,n);
    }
}t;
int a[maxn],lst[maxn],nxt[maxn];
int now[maxn];
int nums[maxn],cur;
pair<int,int> x[maxn];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    k++;
    t.n=n;
    for(int i=1;i<=n;i++)
        scanf("%d",a+i),nums[i]=a[i];
    cur=n;
    sort(nums+1,nums+cur+1);
    cur=unique(nums+1,nums+cur+1)-nums-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(nums+1,nums+cur+1,a[i])-nums;
    for(int i=1;i<=n;i++)
        x[i].first=a[i],x[i].second=i;
    sort(x+1,x+n+1);
    for(int i=1;i<=n;i++){
        lst[i]=now[a[i]];
        nxt[now[a[i]]]=i;
        now[a[i]]=i;
    }
    for(int i=1;i<=n;i++)
        if (!nxt[i]){
            //printf("%d\n",i);
            t.add(i,1);
        }
    int ans=0;
    for(int i=n;i>=1;i--){
        int q=t.rank(i),y=q>k?t.kth(q-k):0;
        int r=upper_bound(x+1,x+n+1,make_pair(a[i],i))-x-1,l=upper_bound(x+1,x+n+1,make_pair(a[i],y))-x-1;
        //printf("i=%d q=%d y=%d l=%d r=%d\n",i,q,y,l,r);
        ans=max(ans,r-l);
        if (lst[i])
            t.add(lst[i],1);
    }
    printf("%d",ans);
}

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://q234rty.top/2016/12/31/bzoj3048/