题解：P11012 「ALFR Round 4」B 颜料

_LSA_ · 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;
}