cfpart1
2025-09-14 22:52:13 #cf

1. 1050div4e

题目描述

给定$cnt[x]$表示$x$的次数,数组$a[i]$,求$a[i]$的子数组$a[l..r]$的个数,使得$\forall i \in[l,r],fre[a[i]]\leq cnt[a[i]]$

解法

  1. 一个很自然的想法是枚举左边界$l$,每次固定左边界$l$,右边界$r$从头($l$)开始遍历,直到不满足条件为止,复杂度$\Theta(n^2)$
  2. 在此基础上进行一些简单的优化,如果[$l,r$]满足条件,那么[$l+1,r$]也满足条件,因此右边界$r$不需要每次从头开始遍历,而是从上一次的$r$开始遍历,复杂度$\Theta(n)$
  3. 具体实现的时候,我们有一个更加规范的思路:$r$从头开始逐渐递增,维护$l$,循环移动$l$直到满足条件,对应右边界$r$对于答案的贡献为$r-l+1$,复杂度$\Theta(n)$

Code

ACCode 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int MAXN=1e5+5;
#define ll long long
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int TT;
    cin>>TT;
    while(TT--){
        int n,k;
        cin>>n>>k;
        vector<int> a(n+1);
        vector<int> cnt(n+1);
        for(int i=1;i<=n;i++)cin>>a[i],cnt[a[i]]++;
        bool flag=true;
        for(int i=1;i<=n;i++){
            if(cnt[i]%k!=0){
                flag=false;
                break;
            }
        }
        if(!flag){
            cout<<"0\n";
            continue;
        }
        for(int i=1;i<=n;i++){
            cnt[i]/=k;
        }
        vector<int> seen(n+1);
        int l=1;
        ll ans=0;
        for(int r=1;r<=n;r++){
            seen[a[r]]++;
            while(seen[a[r]]>cnt[a[r]]){
                seen[a[l]]--;
                l++;
            }
            ans+=r-l+1;
        }
        cout<<ans<<'\n';
    }
}

Prev