https://ac.nowcoder.com/acm/contest/11175

D - 数学家的迷题

 

题意：给定一个数组 aa，两种操作：将 a[id]a[id] 改为 xx；查询 ∏i=lra[i]\prod_{i=l}^ra[i] 的素因子个数。n,q≤5∗104,a[i],x≤105n,q\le 5*10^4,a[i],x\le 10^5.

线段树+bitset

10510^5 内大约有 10410^4 个质数。用 10410^4 位的bitset代表。

线段树每个节点维护该节点上的bitset，向上合并时取或。

起初想分块，但是 n\sqrt{n} 的复杂度还是不够，必须 log⁡\log。

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>

#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n, q;
int a[N];
int vis[N], tot, prime[N];

void pre(int n) {
    for (int i = 2; i <= n; i++) {
        if (!vis[i])prime[tot++] = i;
        int d;
        for (int j = 0; j < tot && (d = i * prime[j]) <= n; j++) {
            vis[d] = 1;
            if (i % prime[j] == 0)break;
        }
    }
}

#define mid ((l+r)>>1)
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
typedef bitset<9600> bits;
bits tr[50005 << 2];

bits gt(int x) {
    bits res = 0;
    for (int i = 0; i < tot && prime[i] * prime[i] <= x; i++) {
        if (x % prime[i] == 0) {
            res[i] = 1;
            while (x % prime[i] == 0)x /= prime[i];
        }
    }
    if (x != 1)res[lower_bound(prime, prime + tot, x) - prime] = 1;
    return res;
}

void up(int rt) {
    tr[rt] = tr[rt << 1] | tr[rt << 1 | 1];
}

void build(int l, int r, int rt) {
    if (l == r) {
        tr[rt] = gt(a[l]);
        return;
    }
    build(lson);
    build(rson);
    up(rt);
}

void upd(int q, int l, int r, int rt) {
    if (l == r) {
        tr[rt] = gt(a[l]);
        return;
    }
    if (q <= mid)upd(q, lson);
    else upd(q, rson);
    up(rt);
}

bits qry(int ql, int qr, int l, int r, int rt) {
    if (ql <= l && qr >= r) {
        return tr[rt];
    }
    bits res = 0;
    if (ql <= mid)res |= qry(ql, qr, lson);
    if (qr > mid)res |= qry(ql, qr, rson);
    return res;
}

int main() {
    pre(100000);
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
    build(1, n, 1);
    while (q--) {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if (op == 1) {
            a[l] = r;
            upd(l, 1, n, 1);
        } else {
            bits ans = qry(l, r, 1, n, 1);
            printf("%d\n", ans.count());
        }
    }
    return 0;
}

 

E - 音游家的谱面(Easy version)

 

题意：nn 根轨道，mm 个音符，初始左手在11号轨道，右手在 nn 号轨道，每秒两只手都可以向任意方向移动一格或不动，按照时间顺序给出了 mm 个音符出现在几号轨道，要求输出每个音符的出现时间，满足能够全部接到且完成时间最短。1≤n,m≤1001\le n,m\le 100

dp

dp[i][j][k]dp[i][j][k] 表示左手在 ii，右手在 jj，完成前 kk 个音符，需要的最短时间。

但是不需要把每个 i,ji,j 都填上，只需要考虑 i=a[k]i=a[k] 或 j=a[k]j=a[k] 时的情况。这样就能跳过中间的移动过程。

最后输出dp路径。

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
#include <bits/stdc++.h>

#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;

int n, m;
int a[N], dp[110][110][110];
typedef pair<int, int> pii;
pii f[110][110][110];

void pr(int u, int v, int k) {
    if (k == 1) {
        printf("%d ", dp[u][v][k]);
        return;
    }
    pr(f[u][v][k].first, f[u][v][k].second, k - 1);
    printf("%d ", dp[u][v][k]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)scanf("%d", &a[i]);
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        dp[a[1]][i][1] = max(a[1] - 1, n - i);
        dp[i][a[1]][1] = max(i - 1, n - a[1]);
    }
    for (int k = 2; k <= m; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dp[a[k]][i][k] > dp[a[k - 1]][j][k - 1] + max(abs(a[k] - a[k - 1]), abs(i - j))) {
                    dp[a[k]][i][k] = dp[a[k - 1]][j][k - 1] + max(abs(a[k] - a[k - 1]), abs(i - j));
                    f[a[k]][i][k] = {a[k - 1], j};
                }
                if (dp[a[k]][i][k] > dp[j][a[k - 1]][k - 1] + max(abs(a[k] - j), abs(i - a[k - 1]))) {
                    dp[a[k]][i][k] = dp[j][a[k - 1]][k - 1] + max(abs(a[k] - j), abs(i - a[k - 1]));
                    f[a[k]][i][k] = {j, a[k - 1]};
                }
                if (dp[i][a[k]][k] > dp[a[k - 1]][j][k - 1] + max(abs(i - a[k - 1]), abs(a[k] - j))) {
                    dp[i][a[k]][k] = dp[a[k - 1]][j][k - 1] + max(abs(i - a[k - 1]), abs(a[k] - j));
                    f[i][a[k]][k] = {a[k - 1], j};
                }
                if (dp[i][a[k]][k] > dp[j][a[k - 1]][k - 1] + max(abs(i - j), abs(a[k] - a[k - 1]))) {
                    dp[i][a[k]][k] = dp[j][a[k - 1]][k - 1] + max(abs(i - j), abs(a[k] - a[k - 1]));
                    f[i][a[k]][k] = {j, a[k - 1]};
                }
            }
        }
    }
    int ans = INF;
    for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)ans = min(ans, dp[i][j][m]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (dp[i][j][m] == ans) {
                pr(i, j, m);
                return 0;
            }
        }
    return 0;
}

 

F - 音游家的谱面(Hard version)

题意：同上。1≤n,m≤5∗1031\le n,m\le 5*10^3

上一题中分别记录了两只手的位置，但是由于只用到了 i=p[k]i=p[k] 或 j=p[k]j=p[k] 时的 i,ji,j，因此可以去掉一维，只保留 dp[i][k]dp[i][k] 表示一只手在 p[k]p[k]，另一只手在 ii，完成前 kk 个音符，需要的最短时间。

设完成第 k−1k-1 轮时一只手在 p[k−1]p[k-1]，另一只手在 jj，完成第 kk 轮时一只手在 p[k]p[k]，另一只手在 ii.

枚举 jj，更新 dp[i][k]dp[i][k]。

假设位于 jj 的手移动到 p[k]p[k]，位于 p[k−1]p[k-1] 的手移动到 ii，则对于满足 ∣i−p[k−1]∣≤∣p[k]−j∣|i-p[k-1]|\le |p[k]-j| 的 ii，转移方程为 dp[i][k]=dp[j][k−1]+∣p[k]−j∣dp[i][k]=dp[j][k-1]+|p[k]-j|，因此这里是一个区间更新，对于这个区间中的所有 ii，dp 值与 dp[j][k−1]+∣p[k]−j∣dp[j][k-1]+|p[k]-j| 比较，取min。

假设位于 jj 的手移动到 ii，位于 p[k−1]p[k-1] 的手移动到 p[k]p[k]，则同理，对于满足 ∣i−j∣≤∣p[k−1]−p[k]∣|i-j|\le |p[k-1]-p[k]| 的 ii，转移方程为 dp[i][k]=dp[j][k−1]+∣p[k−1]−p[k]∣dp[i][k]=dp[j][k-1]+|p[k-1]-p[k]|，同样是一个区间更新。

那么对于不在上面提到的两个区间里的 ii 呢？不需要考虑，因为一定会有其他的 jj 能够包含这些 ii，而这些 jj 之间的关系已经在上一轮全部确定好了，所以可以认为从其它 jj 转移可以等价于从这个 jj 转移。

这两个区间更新就可以用线段树实现，再单点查询dp值。

虽然是区间操作但其实不需要lazy标记，因为是取min而不是区间加或者区间赋值之类，取min的话值只会不断减小，所以只要从上往下走的同时记录路径上的最小值即可。

但是仍然会T。因为复杂度是 O(nmlog⁡n)O(nm\log 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
83
84
85
86
87
88
#include <bits/stdc++.h>

#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;

int n, m;
int p[N], dp[5005][5005], f[5005][5005];

void pr(int u, int k) {
    if (k == 1) {
        printf("%d ", dp[u][k]);
        return;
    }
    pr(f[u][k], k - 1);
    printf("%d ", dp[u][k]);
}

#define mid ((l+r)>>1)
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
pii tr[N << 2];

void build(int l, int r, int rt) {
    tr[rt] = {INF, -1};
    if (l == r) {
        return;
    }
    build(lson);
    build(rson);
}

void upd(int ql, int qr, pii x, int l, int r, int rt) {
    if (ql <= l && qr >= r) {
        tr[rt] = min(tr[rt], x);
        return;
    }
    if (ql <= mid)upd(ql, qr, x, lson);
    if (qr > mid)upd(ql, qr, x, rson);
}

pii qry(int q, int l, int r, int rt) {
    if (l == r) {
        return tr[rt];
    }
    if (q <= mid)return min(tr[rt], qry(q, lson));
    else return min(tr[rt], qry(q, rson));
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)scanf("%d", &p[i]);
    p[0] = 1;
    memset(dp, 0x3f, sizeof(dp));
    dp[n][0] = 0;
    for (int k = 1; k <= m; k++) {
        build(1, n, 1);
        for (int j = 1; j <= n; j++) {
            int tL = abs(p[k] - p[k - 1]);
            int L = max(1, j - tL), R = min(n, j + tL);
            upd(L, R, {dp[j][k - 1] + tL, j}, 1, n, 1);
            tL = abs(p[k] - j);
            L = max(1, p[k - 1] - tL), R = min(n, p[k - 1] + tL);
            upd(L, R, {dp[j][k - 1] + tL, j}, 1, n, 1);
        }
        for (int i = 1; i <= n; i++) {
            pii t = qry(i, 1, n, 1);
            dp[i][k] = t.first;
            f[i][k] = t.second;
        }
    }
    int ans = INF;
    for (int i = 1; i <= n; i++)ans = min(ans, dp[i][m]);
    for (int i = 1; i <= n; i++) {
        if (dp[i][m] == ans) {
            pr(i, m);
            return 0;
        }
    }
    return 0;
}

 

单调队列+前缀和

更新时用线段树还是不行，必须用线性复杂度的方法。还是分两种情况考虑更新：

假设位于 jj 的手移动到 p[k]p[k]，位于 p[k−1]p[k-1] 的手移动到 ii。对于满足 ∣i−p[k−1]∣≤∣p[k]−j∣|i-p[k-1]|\le |p[k]-j| 的 ii，转移方程为 dp[i][k]=dp[j][k−1]+∣p[k]−j∣dp[i][k]=dp[j][k-1]+|p[k]-j|。设 ∣p[k]−j∣=tL|p[k]-j|=tL，那么也就是要更新 i∈[p[k−1]−tL,p[k−1]+tL]i\in[p[k-1]-tL,p[k-1]+tL]。对于所有的 jj，这个区间都包含 p[k−1]p[k-1]，所以可以用 p[k−1]p[k-1] 把区间分成两块，左部分求前缀最小值，右部分求后缀最小值。即对于一个 jj，在 p[k−1]−tLp[k-1]-tL 和 p[k−1]+tLp[k-1]+tL 处记下 dp[j][k−1]+tLdp[j][k-1]+tL，再枚举 ii 求 dp[i][k]dp[i][k]，若 ii 位于 p[k−1]p[k-1] 左侧，则等于 ii 处的前缀最小值，否则等于 ii 处的后缀最小值。

假设位于 jj 的手移动到 ii，位于 p[k−1]p[k-1] 的手移动到 p[k]p[k]，之前是用 jj 去更新 dp[i][k]dp[i][k]，现在反过来考虑 ii 会被哪些 jj 更新到。∣p[k]−p[k−1]∣|p[k]-p[k-1]| 是一个常数，设为 CC，则 ii 会被 [i−C,i+C][i-C,i+C] 这个范围内的 jj 更新到。这就是一个固定大小的窗口。要对每一个 ii 求它所在窗口的最小值，就是典型的单调队列。维护一个递增的单调队列，满足首尾到 ii 的距离不超过 CC，队首就是窗口中的最小值。

本题还是比较卡常的，dp[i][k]dp[i][k] 要改为 dp[k][i]dp[k][i]。

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
#include <bits/stdc++.h>

#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;

int n, m;
int p[N], dp[5005][5005], f[5005][5005];

void pr(int u, int k) {
    if (k == 1) {
        printf("%d ", dp[k][u]);
        return;
    }
    pr(f[k][u], k - 1);
    printf("%d ", dp[k][u]);
}

pii q[N], d[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)scanf("%d", &p[i]);
    p[0] = 1;
    memset(dp, 0x3f, sizeof(dp));
    dp[0][n] = 0;
    for (int k = 1; k <= m; k++) {
        int tail = 0, head = 1, cur = 1;
        int tL = abs(p[k] - p[k - 1]);
        for (int i = 1; i <= n; i++) {
            while (cur <= n && cur - i <= tL) {
                while (tail - head + 1 > 0 && q[tail].first >= dp[k - 1][cur] + tL)tail--;
                q[++tail] = {dp[k - 1][cur] + tL, cur};
                cur++;
            }
            while (tail - head + 1 > 0 && i - q[head].second > tL)head++;
            if (tail - head + 1 > 0) {
                dp[k][i] = q[head].first;
                f[k][i] = q[head].second;
            }
        }
        for (int i = 1; i <= n; i++)d[i] = {INF, -1};
        for (int j = 1; j <= n; j++) {
            tL = abs(p[k] - j);
            int L = max(1, p[k - 1] - tL), R = min(n, p[k - 1] + tL);
            d[L] = min(d[L], {dp[k - 1][j] + tL, j});
            d[R] = min(d[R], {dp[k - 1][j] + tL, j});
        }
        for (int i = 2; i <= p[k - 1]; i++)d[i] = min(d[i], d[i - 1]);
        for (int i = n - 1; i >= p[k - 1]; i--)d[i] = min(d[i], d[i + 1]);
        for (int i = 1; i <= n; i++) {
            if (dp[k][i] > d[i].first) {
                dp[k][i] = d[i].first;
                f[k][i] = d[i].second;
            }
        }
    }
    int ans = INF;
    for (int i = 1; i <= n; i++)ans = min(ans, dp[m][i]);
    for (int i = 1; i <= n; i++) {
        if (dp[m][i] == ans) {
            pr(i, m);
            return 0;
        }
    }
    return 0;
}