好数组——尺取法

好数组

给定一个长度为 n 的数组 a，计算数组 a 中所有子数组中好数组的数目。

好数组定义如下：

对于数组 al ,al+1, ⋯ ,ar ，若数组中所有数的质因数种类数不超过 k，则称为好数组。

Input

输入的第一行包含两个正整数 n,k (1≤k≤n≤10^5)

输入的第二行包含 n 个正整数 ai(1≤ ai ≤100)

Output

输出数组 

a 中所有子数组中好数组的数目。

样例输入

4 2
2 6 5 15

样例输出

6 

样例：

对于所有子数组：

[2]
[2,6]
[2,6,5]
[2,6,5,15]
[6]
[6,5]
[6,5,15]
[5]
[5,15]
[15]

k=2，所以除了 [2,6,5],[2,6,5,15],[6,5,15],[6,5] 这四个子数组其他都是符合的。

解析：

尺取法：像尺子一样取一段，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法。

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
priority_queue<int,vector<int>,greater<int>> ll;
priority_queue<int> rr;
typedef pair<int,int> PII;
const int N=1e5+10;
int n,k;
vector <int> prime[N];
int a[N];
map <int,int> q;
void get_prime(int n)
{int m=n;for (int i=2;i<=n/i;i++){if (n%i==0){prime[m].push_back(i);while (n%i==0) n /=i;}}if (n>1) prime[m].push_back(n);
}
signed main()
{ios;cin>>n>>k;for (int i=1;i<=n;i++){cin>>a[i];if (prime[a[i]].size()==0) get_prime(a[i]);}int cnt=0;for (int r=1,l=1;r<=n;r++){for (int i=0;i<prime[a[r]].size();i++) q[prime[a[r]][i]]++;    while (q.size()>k)             //当种类数大于 k 时，就从当前 l 开始，减去a[l]的质数，直到种类数小于等于 k 为止{   for (int i=0;i<prime[a[l]].size();i++) {q[prime[a[l]][i]]--;if (q[prime[a[l]][i]]==0) q.erase(prime[a[l]][i]);}l++;}cnt +=r-l+1;}cout<<cnt;return 0;
}