30pts求助 P3419

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int color;
}b[100005];
int n,k,tot,p,ans,qwq[100005],a[500005],nex[500005],color[100005];
bool bj[100005];
inline bool pd(int x,int y){
    return qwq[b[x].color]<qwq[b[y].color];
}
inline void work1(int x){
    if(x*2+1<=tot&&pd(x,x*2+1)&&pd(x*2,x*2+1)){
        swap(b[x],b[x*2+1]);
        swap(color[b[x].color],color[b[x*2+1].color]);
        work1(tot*2+1);
    }
    else if(x*2<=tot&&pd(x,x*2)){
        swap(b[x],b[x*2]);
        swap(color[b[x].color],color[b[x*2].color]);
        work1(x*2);
    }
}
inline void work(int x){
    if(x!=1&&pd(x/2,x)){
        swap(b[x],b[x/2]);
        swap(color[b[x].color],color[b[x/2].color]);
        work(x/2);
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k>>p;
    for(int i=1;i<=p;i++){
        cin>>a[i];
        if(color[a[i]]){
            nex[color[a[i]]]=i;
        }
        color[a[i]]=i;
    }
    for(int i=1;i<=p;i++){
        // for(int i=1;i<=n;i++){
        //     cout<<bj[i];
        // }
        // cout<<'\n';
        // if(i==8){
        //     for(int i=1;i<=tot;i++){
        //         cout<<b[i].color<<' '<<qwq[b[i].color]<<'\n';
        //     }
        // }
        if(nex[i]==0){
            nex[i]=1e9;
        }
        if(bj[a[i]]){
            qwq[a[i]]=nex[i];
            work(color[a[i]]);
        }
        else{
            // cout<<i<<'\n';
            ans++;
            qwq[a[i]]=nex[i];
            if(tot<k){
                b[++tot]={a[i]};
                color[a[i]]=tot;
                work(tot);
                bj[a[i]]=1;
            }
            else{
                bj[b[1].color]=0;
                // cout<<b[1].color<<'\n';
                bj[a[i]]=1;
                swap(color[b[1].color],color[b[tot].color]);
                swap(b[1],b[tot]);
                --tot;
                work1(1);
                b[++tot]={a[i]};
                color[a[i]]=tot;
                work(tot);
            }
        }
    }
    cout<<ans;
    return 0;
}