题解：P11455 [USACO24DEC] Cowdependence G

· · 题解

考虑根号分治，把 x 按照阈值 B 分成大 x 和小 x。

对于小 x，其只有 B 种，可以直接枚举所有 x 然后贪心对每种颜色做处理。处理方法就是对于一个左端点，暴力往右扫，直到距离 > x 再新开一段。这样总时间复杂度为 \mathcal{O}(B \cdot \sum cnt_c) = \mathcal{O}(nB)。

对于大 x，最后的答案一定不会超过 \frac{n}{x} \leq \frac{n}{B}。因此不妨 \mathcal{O}(n) 枚举所有的颜色，然后二分 \mathcal{O}(\frac{cnt_c}{B}) 个答案改变的地方，单次二分的时间复杂度为 \mathcal{O}(\log cnt_c)。利用 \sum cnt_c = n，可以得到时间复杂度为 \mathcal{O}(n\frac{n}{B}\log n)。

利用均值不等式，可得：

nB + n\frac{n}{B}\log n \geq 2\sqrt{nB \times n\frac{n}{B}\log n} = 2n\sqrt{n \log n}

当且仅当 nB = n\frac{n}{B}\log n，即 B = \sqrt{n \log n} 时取等。

故总时间复杂度为 \mathcal{O}(n \sqrt{n \log n})，在 B = \sqrt{n \log n} 时取到。

最后可以使用差分维护区间加答案，复杂度线性。

#include<bits/stdc++.h>
// #define int long long
#define fo(i, l, r) for(decltype((l) + (r)) i = (l); i <= (r); ++i)
#define fd(i, l, r) for(decltype((l) + (r)) i = (l); i >= (r); --i)
#define fu(i, l, r) for(decltype((l) + (r)) i = (l); i <  (r); ++i)
#define y1 zhang_kevin
#define pii pair<int, int>
#define fi first
#define se second
#define vec vector
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ull unsigned long long
#define flush() (fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf)
#define puts wrs
using namespace std;
bool ST;
char ibuf[1 << 20], *p1 = ibuf, *p2 = ibuf, obuf[1 << 20], *p3 = obuf;
inline char gc(){
    if(p1 == p2){
        p1 = ibuf, p2 = ibuf + fread(ibuf, 1, 1 << 20, stdin);
        if(p1 == p2) return EOF;
        return *p1++;
    }
    return *p1++;
}
inline char pc(char ch){
    if(p3 == obuf + (1 << 20)) flush();
    *p3 = ch;
    return *p3++;
}
template<typename type>
inline int rd(type &x){
    x = 0; bool f = 0; char ch = gc();
    while(!isdigit(ch)) f |= ch == '-', ch = gc();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
    return f ? x = -x : 0;
}
template<typename type, typename ...T>
inline void rd(type &x, T &...y){rd(x), rd(y...);}
class Flush{public: ~Flush(){flush();}}_;
template<typename type>
inline void wr(type x){
    if(x < 0) pc('-'), x = -x;
    if(x > 9) wr(x / 10);
    pc(x % 10 + '0');
    return;
}
inline void wrs(const string& s){for(auto ch : s) pc(ch);}
namespace Solution{
    const int B = 2500;
    int n, a[100005], ans[100005];
    vec<int> box[100005];
    inline int calc(int c, int x){
        int l = box[c][0], cnt = 1;
        for(auto i : box[c]){
            if(i - l > x){
                cnt++;
                l = i;
            }
        }
        return cnt;
    }
    inline void Solve(){
        rd(n); fo(i, 1, n) rd(a[i]), box[a[i]].pb(i);
        fu(x, 1, B){
            fo(c, 1, n){
                if(box[c].empty()) continue;
                int cnt = calc(c, x);
                ans[x] += cnt, ans[x + 1] -= cnt;
            }
        }
        fo(c, 1, n){
            if(box[c].empty()) continue;
            int x = B;
            while(x <= n){
                int l = x, r = n, res = l, t = calc(c, x);
                while(l <= r){
                    int mid = (l + r) >> 1;
                    if(calc(c, mid) == t) l = mid + 1, res = mid;
                    else r = mid - 1;
                }
                ans[x] += t, ans[res + 1] -= t, x = res + 1;
            }
        }
        fo(i, 1, n) wr(ans[i] += ans[i - 1]), pc('\n');
        return;
    }
}
bool ED;
signed main(){
    clock_t START = clock();
    // freopen("input.in", "r", stdin), freopen("output.out", "w", stdout);
    Solution::Solve();
    cerr << (double)(clock() - START) / CLOCKS_PER_SEC << " s" << '\n';
    cerr << 1.0 * abs(&ED - &ST) / 1024 / 1024 << " MB" << '\n';
    return 0;
}