CF2149E Hidden Knowledge of the Ancients 题解

TempestMiku · 2025-10-10 18:07:31 · 题解

Codeforce

题意概括: 寻找数列 a 中有多少区间满足以下条件

区间内包括 k 个不同整数

区间长度在 l 与 r 之间

题解

可以使用滑动窗口思想考虑，固定右端点，寻找合法的左端点范围。

例如 k=2 ，对于 i=5 的时候，合法区间是蓝色框内。

于是我们可以使用两个数组，一个来记录合法区间的左端点，一个来记录合法区间的右端点。

然后因为固定了右端点，在结合题目要求区间长度在 l 和 r 内的要求取一下即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int a[N];
int lk[N],rk[N];
int T,n,k,l,r;
map<int,int> m;
inline void solve(){
    m.clear();
    cin>>n>>k>>l>>r;
    for( int i=1;i<=n;i++){
        cin>>a[i];
        lk[i]=0,rk[i]=0;
    }
    int j=1;
    for( int i=1;i<=n;i++){
        m[a[i]]++;
        while(m.size()>k){
            if(!--m[a[j]]){
                m.erase(a[j])//map的size()也记录某个地方是0的情况，所以得使用erase()

            }
            j++;
        }
        if(m.size()==k){
            lk[i]=j;
        }
    }
    m.clear();
    j=1;
    for( int i=1;i<=n;i++){
        m[a[i]]++;
        while(m.size()>=k){
            if(!--m[a[j]]){
                m.erase(a[j]);
            }
            j++;
        }
        if(j){//先向右找到合法区间右端点的右边一个，再往左走一步
            j--;
            m[a[j]]++;
            if(m.size()==k){
                rk[i]=j;
            }
        }
    }
    int ans=0;
    for( int i=1;i<=n;i++){
        int ll=max(lk[i],i-r+1);
        int rr=min(rk[i],i-l+1);
        if(ll){//避免ll=0,rr=0的情况导致ans加上1
            ans+=max(rr-ll+1,0ll);
        }
    }
    cout<<ans<<endl;
}
signed main(void){
    cin.tie(NULL)->sync_with_stdio(false);//输入加速
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}