滑动窗口计算方案数

题目传送门

大致思路

利用前缀和计算前 $i$个数有多少满足最低消费不超过 $p$ 的,便于区间内的快速查询
枚举每一个 $k$ , 获取对应下标,利用双指针 O(n) 计算方案数:
当窗口中没有 最低消费不超过 $p$ 的 右指针就往右移动
否则 $ans+=sz-right$

Code

void solve(){
    int n,k,p;
    cin>>n>>k>>p;
    vector<int> a(n+1),b(n+1);
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    vector<int> cnt(n+1);
    for(int i=1;i<=n;i++) cnt[i]=cnt[i-1]+(b[i]<=p?1:0);
    int ans=0;
    for (int i=0;i<k;i++) {
        vector<int> t={0};
        for (int j=1;j<=n;j++) if (a[j]==i) t.pb(j);
        int sz=t.size();
        if (sz<3) continue;
        int right=2;
        for (int left=1;left<sz;left++) {
            while (right<sz && (cnt[t[right]]-cnt[t[left]-1]<1|| right==left )) right++;
            if (right==sz) break;
            ans+=(sz-right);
        }
    }
    cout<<ans<<el;
}