Goose, goose, DUCK?：扫描线基础板题。
题目要求的是满足任意一个元素都不出现 \(k\) 次的区间个数，直接做不好做，因此考虑正难则反，转化为至少有一个数出现 \(k\) 次的区间个数。
先对某一种元素进行考虑，显然我们从中选出恰好有 \(k\) 个该元素的区间，区间的左端点和右端点有一个取值的区间。这启示我们考虑一个常见的 trick：把区间的左端点看做横坐标，右端点看做纵坐标，把区间拍在一个二维平面上，这样一个区间就被转化为了一个矩形。
因此对每一个元素算出恰有 \(k\) 个的取值区间，转化为矩形后用线段树维护矩形面积和即可。最后答案即为 \(\dfrac{n(n+1)}{2}\times ans\)，其中 \(ans\) 为被矩形覆盖的面积。
时间复杂度 \(O((n + V)\log n)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc (p << 1)
#define rc ((p << 1) | 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int N = 1000005;
int n, m, a[N];
ll ans;
struct Node{int l, r;ll len, sm;
};
struct Segtree{Node tr[4 * N];void pushup(int p){if(tr[p].sm) tr[p].len = (tr[p].r - tr[p].l + 1);else{tr[p].len = 0;if(lc < 4 * N) tr[p].len += tr[lc].len;if(rc < 4 * N) tr[p].len += tr[rc].len;}}void build(int p, int ln, int rn){tr[p] = {ln, rn, 0, 0};if(ln == rn) return;int mid = (ln + rn) >> 1;build(lc, ln, mid);build(rc, mid + 1, rn);pushup(p);}void update(int p, int ln, int rn, int k){if(ln <= tr[p].l && tr[p].r <= rn){tr[p].sm += k;pushup(p);return;}int mid = (tr[p].l + tr[p].r) >> 1;if(ln <= mid) update(lc, ln, rn, k);if(rn >= mid + 1) update(rc, ln, rn, k);pushup(p);}
}tr1;
struct Line{int l, r, v;
};
vector<Line> line[N];
vector<int> pos[N];
int main()
{//freopen("sample.in", "r", stdin);//freopen("sample.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;ans = 1ll * n * (n + 1) / 2;for(int i = 1; i <= 1e6; i++)pos[i].push_back(0);for(int i = 1; i <= n; i++){cin >> a[i];pos[a[i]].push_back(i);}for(int i = 1; i <= 1e6; i++)pos[i].push_back(n + 1);for(int i = 1; i <= 1e6; i++){for(int j = 1; j + m - 1 < pos[i].size() - 1; j++){int lx = pos[i][j - 1] + 1, rx = pos[i][j], ly = pos[i][j + m - 1], ry = pos[i][j + m] - 1;line[lx].push_back({ly, ry, 1});line[rx + 1].push_back({ly, ry, -1});}}tr1.build(1, 1, n);for(int i = 1; i <= n; i++){for(auto ln : line[i])tr1.update(1, ln.l, ln.r, ln.v);ans -= tr1.tr[1].len;}cout << ans;return 0;
}