自动搬运

查看原文

来自洛谷，原作者为

	LSA AFO||ds和数数学不会

搬运于2025-08-24 23:03:28，当前版本为作者最后更新于2024-08-30 21:42:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

这题明明可以做到线性怎么包括官解都写的树状数组qwq。

首先，由于选择的区间是连续的一段，而且对于每个左端点 $l$，其对应满足权值超过 $k$ 的最小的右端点 $r$ 是显然单调的，所以考虑双指针，到这里根官方题解是一样的。

接下来考虑每次移动指针怎么更新权值。

记 $sz_i$ 为当前每个颜色出现的次数，$cnt_i$ 为 $sz_j \geq i$ 的 $j$ 的个数，就是颜色出现次数超过 $i$ 的颜色个数。

由于双指针移动时 $sz_{a_i}$ 只会变化 $1$，所以这两个数组是很容易维护的。

每次 $r$ 向右扩展时（这里的 $sz_{a_r}$ 还没更新），对于 $sz_x \le sz_{a_r}$ 的颜色 $x$ 是没有影响的，因为它们的 $\min$ 不变；而对于 $sz_x > sz_{a_r}$ 的颜色 $x$，由于 $\min(sz_{a_r}+1,sz_x) = \min(sz_{a_r},sz_x)+1$，所以权值会增加 $cnt_{sz_{a_r}+1}$。$l$ 的扩展是同理的。

时间复杂度 $O(n)$。

代码实现中是先更新 $sz$ 再更新权值的，跟上面的描述有点区别。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read(){
    ll X = 0 ,r = 1;
    char ch = getchar();
    while(!isdigit(ch) && ch != '-') ch = getchar();
    if(ch == '-') r = -1,ch = getchar();
    while(isdigit(ch)) X = X*10+ch-'0',ch = getchar();
    return X*r;
}
const int N = 2e6+10;
int n,a[N],m;
int cnt[N],sz[N];
ll k;
int main(){
	n = read(); k = read();
	for(int i=1;i<=n;i++) a[i] = read();
	int ans = n+1;
	ll res = 0;
	for(int l=1,r=0;l<=n;l++){
		while(r < n && res < k){
			r++; sz[a[r]]++;
			cnt[sz[a[r]]]++;
			res += cnt[sz[a[r]]]-1;
		}
		if(res >= k) ans = min(ans,r-l+1);
		res -= cnt[sz[a[l]]]-1;
		cnt[sz[a[l]]]--; sz[a[l]]--;
	}
	printf("%d",ans == n+1 ? -1 : ans);
    return 0;
}