给定一个值域在 \([1,\ m]\) 的长度为 \(n\) 的正整数序列 \(a_i\) ，求出最长的子序列满足：\[\forall x\in[1,\ m],\ \displaystyle\sum_{i=l}^r[a_i=x]=0,\ or \displaystyle\sum_{i=l}^r[a_i=x]\ge k\]
\(n,\ m,\ k\leq10^5\)
数据结构
考虑对于每个右端点 \(i\) ，不合法的区间为 \([i\) 的上 \(k-1\) 次出现的位置 \(+1\) \(,\ i]\) 。考虑对于这一段区间打 \(+1\) 标记，询问合法的区间即为找到最小的为 \(0\) 的位置，可以用线段树维护。由于只需要考虑不同的数的贡献，因此每次修改需要将上一次修改撤销。
时间复杂度 \(O(n\log n)\)
代码
#includeusing namespace std;const int maxn = 1e5 + 10;int n, m, k, a[maxn], pos[maxn], pre[maxn], lst[maxn];vector vec[maxn];#define mid ((l + r) >> 1)#define lson k << 1, l, mid#define rson k << 1 | 1, mid + 1, rint tag[maxn << 2], val[maxn << 2];inline void pushtag(int k, int x) { tag[k] += x, val[k] += x;}inline void pushdown(int k) { int &x = tag[k]; if (x) { pushtag(k << 1, x); pushtag(k << 1 | 1, x); x = 0; }}inline void maintain(int k) { val[k] = min(val[k << 1], val[k << 1 | 1]);}void upd(int k, int l, int r, int ql, int qr, int x) { if (ql <= l && r <= qr) { pushtag(k, x); return; } pushdown(k); if (ql <= mid) upd(lson, ql, qr, x); if (qr > mid) upd(rson, ql, qr, x); maintain(k);}int query(int k, int l, int r) { if (l == r) return l; pushdown(k); assert(val[k] >= 0); if (val[k]) return n + 1; return val[k << 1] ? query(rson) : query(lson);}#undef mid#undef lson#undef rsoninline void add(int x, int v) { if (x) upd(1, 1, n, lst[x] + 1, x, v);}void solve() { memset(pos, 0, (n + 1) << 2); memset(lst, 0, (n + 1) << 2); memset(tag, 0, (n + 1) << 4); memset(val, 0, (n + 1) << 4); for (int i = 1; i <= m; i++) { vec[i].clear(); } for (int i = 1; i <= n; i++) { scanf("%d", a + i); vec[a[i]].push_back(i); pre[i] = pos[a[i]], pos[a[i]] = i; } for (int i = 1; i <= m; i++) { int sz = vec[i].size(); for (int j = k - 1; j < sz; j++) { lst[vec[i][j]] = vec[i][j - k + 1]; } } int ans = 0; for (int i = 1; i <= n; i++) { add(pre[i], -1), add(i, 1); ans = max(ans, i - query(1, 1, n) + 1); } printf("%d\n", ans);}int main() { while (~scanf("%d %d %d", &n, &m, &k)) { solve(); } return 0;}