DDOSvoid's Blog

CF 1603D Artistic Partition

发表于 分类于
本文字数： 4.6k 阅读时长 ≈ 4 分钟

题目描述

https://codeforces.com/problemset/problem/1603/D

简要题意：现在有 $q$ 次询问，每次询问给定 $n$ 和 $k$，求将 $[1,n]$ 这个序列分成 $k$ 段的最小代价和，$[l,r]$ 的代价为 $c(l,r)=\sum_{i=l}^r\sum_{j=i}^r[(i,j)\ge l]$

$k\le n\le 10^5,q\le 3\times 10^5$

Solution

容易发现当 $2^k>n$ 时，答案一定为 $n$，那么我们的 $k$ 就缩小到了 $O(\log n)$ 的级别，我们考虑 $dp$，令 $f_{i,j}$ 表示前 $i$ 个数，分成了 $j$ 段，那么 $f_{i,j}=\min(f_{k,j-1}+c(k+1,i)),k<i$，容易发现转移满足决策单调性，但是 $c(l,r)$ 看起来不是很好求，我们先化简一下 $c(l,r)$，可以得到 $c(l,r)=\sum_{i=l}^rS(\lfloor\frac{r}{i}\rfloor)$，其中 $S(n)=\sum_{i=1}^n\varphi(i)$，我们考虑还是用类似莫队的方法维护 $c(l,r)$，$l$ 移动的时候代价是 $O(1)$ 的，$r$ 移动的时候，所有 $i\ge l,\lfloor\frac{r}{i}\rfloor<\lfloor\frac{r+1}{i}\rfloor$ 的 $i$ 的贡献要改变，容易发现这样的 $i$ 是 $r+1$ 的约数，那么右端点的总移动是 $O(n\log n\ln n)$，我们直接暴力维护这个东西，总的时间复杂度为 $O(n\log^2n\ln n)$，常数非常小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define maxn 100010
#define ll long long
#define INF 1000000000000000000
#define lowbit(i) ((i) & (-i))
using namespace std;

bool isp[maxn]; int pri[maxn], cnt, phi[maxn]; ll s[maxn];
void init_isp(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            } phi[i * pri[j]] = phi[i] * (pri[j] - 1); 
        }
    }
    for (int i = 1; i <= n; ++i) s[i] = phi[i] + s[i - 1]; 
}

int n, k, q;

vector<int> D[maxn];

int l, r; ll sum;
inline void addL(int x) { sum += s[r / x];}
inline void addR(int x) {
    for (auto t : D[x]) {
        if (t < l) break;
        sum += s[r / t] - s[r / t - 1];
    }
}
inline void delL(int x) { sum -= s[r / x]; } 
inline void delR(int x) {
    for (auto t : D[x]) {
        if (t < l) break;
        sum -= s[r / t] - s[r / t - 1]; 
    }
}
void move(int L, int R) {
    while (r < R) ++r, addR(r);
    while (l > L) --l, addL(l);
    while (r > R) delR(r), --r;
    while (l < L) delL(l), ++l;
}

ll f[20][maxn];
void solve(int l, int r, int L, int R, ll *f, ll *g) { // f_i in [l, r], g_j in [L, R] 
    if (l > r) return ; int m = l + r >> 1, p = L;
    for (int i = L; i <= min(R, m - 1); ++i) {
        move(i + 1, m); 
        if (g[i] + sum < f[m]) f[m] = g[i] + sum, p = i;
    }
    solve(l, m - 1, L, p, f, g), solve(m + 1, r, p, R, f, g);
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    n = 100000; k = 18; init_isp(n);
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i) D[j].push_back(i);
    for (int i = 1; i <= n; ++i) reverse(D[i].begin(), D[i].end());
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= k; ++j) f[j][i] = INF;
    f[0][0] = 0; l = r = 1, sum = s[1];
    for (int o = 1; o <= k; ++o) solve(1, n, 0, n - 1, f[o], f[o - 1]);
    cin >> q; 
    for (int i = 1; i <= q; ++i) {
        int x, y; cin >> x >> y;
        if (y > 30 || (1 << y) > x) cout << x << "\n";
        else cout << f[y][x] << "\n";
    }
    return 0;
}

另外我们也可以对于每个右端点语预处理左端点的答案，这样可以做到 $O(n\log^2n+n\sqrt n)$，实际效果不如第一种做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define maxn 100010
#define ll long long
#define INF 1000000000000000000
#define lowbit(i) ((i) & (-i))
using namespace std;

bool isp[maxn]; int pri[maxn], cnt, phi[maxn]; ll s[maxn];
void init_isp(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            } phi[i * pri[j]] = phi[i] * (pri[j] - 1); 
        }
    }
    for (int i = 1; i <= n; ++i) s[i] = phi[i] + s[i - 1]; 
}

struct Div_hash {
    int n, sn;
    vector<ll> pre;
    
    inline int get(int x) { return x <= sn ? x : sn * 2 - n / x + 1; } 
    void init(int _n) {
        n = _n; sn = sqrt(n); pre.resize(2 * sn + 1);
        for (int l = 1, r; l <= n; l = r + 1) {
            r = n / (n / l); 
            pre[get(n / l)] = (r - l + 1) * s[n / l]; 
        }
        for (int i = 1; i <= 2 * sn; ++i) pre[i] += pre[i - 1]; 
    }
    inline ll get_sum(int x) {
        int id = get(n / x), y = n / (n / x);
        return pre[id - 1] + (y - x + 1) * s[n / x];
    }
} h[maxn];

int n, k, q;

ll f[20][maxn];
void solve(int l, int r, int L, int R, ll *f, ll *g) { // f_i in [l, r], g_j in [L, R] 
    if (l > r) return ; int m = l + r >> 1, p = L;
    for (int i = L; i <= min(R, m - 1); ++i) 
        if (g[i] + h[m].get_sum(i + 1) < f[m]) f[m] = g[i] + h[m].get_sum(i + 1), p = i;
    solve(l, m - 1, L, p, f, g), solve(m + 1, r, p, R, f, g);
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    n = 100000; k = 18; init_isp(n);
    for (int i = 1; i <= n; ++i) h[i].init(i);
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= k; ++j) f[j][i] = INF;
    f[0][0] = 0; 
    for (int o = 1; o <= k; ++o) solve(1, n, 0, n - 1, f[o], f[o - 1]);
    cin >> q; 
    for (int i = 1; i <= q; ++i) {
        int x, y; cin >> x >> y;
        if (y > 30 || (1 << y) > x) cout << x << "\n";
        else cout << f[y][x] << "\n";
    }
    return 0;
}