Codeforces Div2 864

发表于 更新于 阅读次数： 本文字数： 6.7k 阅读时长 ≈ 12 分钟

Codeforces Round #864 (Div. 2)

D. Li Hua and Tree

题目大意

李华有一棵$n$个节点的有根树，根节点为$1$，第$i$个节点有点权$a_i$
定义一个非叶子节点的重儿子为其所有儿子里子树大小最大的，若有多个大小相同的则取编号最小的
维护$m$次操作
操作一：求以$x$为根的子树的点权和
操作二：记$x$的父亲为$fa_x$，重儿子为$hs_x$，切断$(x, fa_x)$之间的边，新加一条$(hs_x, fa_x)$之间的边
操作二不保证$x$是叶子节点，若$x$是叶子，就忽略该操作

解题思路

操作二是一个很局部的操作，改变的信息并不多

记$x$的父亲为$f$，重儿子为$v$
对于$f$，这些信息在操作二后可能改变：$hs_f，sons_f$
对于$v$，这些信息在操作二后可能改变：$hs_v，sons_v， sum_v，sz_v，fa_v$
对于$u$，这些信息在操作二后可能改变：$hs_u，sons_u， sum_u，sz_u，fa_u$

每个信息都能以$O(1)$或$O(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
#include <bits/stdc++.h>
using ll = long long;
using PII = std::pair<int, int>;
using PLI = std::pair<ll, int>;
const int N = 1e5 + 10;
int n, m;
int a[N], sz[N], fa[N], hs[N];
ll sum[N];
std::set<PLI> sons[N];
std::vector<int> e[N];
void dfs(int u, int f)
{
    sz[u] = 1, sum[u] = a[u], fa[u] = f;
    for (auto v : e[u])
    {
        if (v == f)
            continue;
        dfs(v, u);
        sz[u] += sz[v];
        sum[u] += sum[v];
        sons[u].insert({-sz[v], v});
        if (sz[v] > sz[hs[u]] || sz[v] == sz[hs[u]] && v < hs[u])
            hs[u] = v;
    }
    return;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    for (int i = 1; i <= n - 1; ++i)
    {
        int u, v;
        std::cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= m; ++i)
    {
        int op, u;
        std::cin >> op >> u;
        if (op == 1)
            std::cout << sum[u] << '\n';
        else
        {
            auto f = fa[u];
            auto v = hs[u];
            if (!v)
                continue;
            
            sons[f].erase({-sz[u], u});    
 
            sz[u] -= sz[v];
            sum[u] -= sum[v];
            sons[u].erase({-sz[v], v});
            hs[u] = sons[u].empty() ? 0 : std::get<1>(*sons[u].begin());
            fa[u] = v;
 
            sz[v] += sz[u];
            sum[v] += sum[u];
            sons[v].insert({-sz[u], u});
            hs[v] = std::get<1>(*sons[v].begin());
            fa[v] = f;
 
            sons[f].insert({-sz[v], v});
            hs[f] = std::get<1>(*sons[f].begin());
        }
    }
    return 0;
}

E. Li Hua and Array

题目大意

$\phi(n)$是$n$的欧拉函数，值为小于等于$n$的，且与$n$互质的正整数个数
李华有一个正整数序列$a$，维护$m$个操作
操作一：对区间$[l,r]$进行区间修改，每个$a_i$变成$\phi(a_i)$
操作二：对于区间$[l,r]$，回答最小修改几次能使得$a_l=a_{l+1}=\cdots=a_r$，每次修改能选中一个$x\in[l,r]$，把$a_x$变成$\phi(a_x)$，只需要回答最小修改次数，并不用真的修改序列

解题思路

考虑另一个类似的问题
操作一：对区间$[l,r]$进行区间修改，每个$a_i$变成$\lceil{\frac{a_i}{2}}\rceil$
操作二：对于区间$[l,r]$，回答最小修改几次能使得$a_l=a_{l+1}=\cdots=a_r$，每次修改能选中一个$x\in[l,r]$，把$a_x$变成$\lceil{\frac{a_x}{2}}\rceil$，只需要回答最小修改次数，并不用真的修改序列

可以发现一个数经过最多$log$次操作一，都会变成$1$并且之后不再改变
考虑建一棵树，对于每个$a_i$，在$a_i$和$\lceil{\frac{a_i}{2}}\rceil$之间建边，$\lceil{\frac{a_i}{2}}\rceil$作为$a_i$的父亲，类似地一层一层往上建，最后一定会变成一个根为$1$的树
此时再看操作二，答案是区间$[l,r]$内所有点跳到同一个点所需的最小次数，其实就是这些点到他们的$lca$的距离之和

首先$lca$先用倍增预处理好，然后考虑用线段树解决这个问题

对于操作一，线段树需要维护的有：区间深度之和$sum$
维护这个主要是因为当一个数变为$1$后，深度不能再变了
同时可以发现这里区间修改并没有使用懒标记，而是直接暴力递归到叶子修改，为什么这样可行呢$?$ 原因放在最后

对于操作二，线段树需要维护的有：区间$lca$，每个区间对操作二的答案$ans$，区间长度$len$
区间$lca$与区间$len$不用赘述
解释一下下面这个对$ans$的$pushup$

1
ans[id] = ans[id << 1] + ans[id << 1 | 1] + len[id << 1] * (dep[lca[id << 1]] - dep[lca[id]]) + len[id << 1 | 1] * (dep[lca[id << 1 | 1]] - dep[lca[id]]);

当前答案由四部分组成，左儿子区间的答案，右儿子区间的答案，左儿子区间$lca$到当前区间$lca$的距离乘以左儿子区间$len$，右儿子区间$lca$到当前区间$lca$的距离乘以右儿子区间$len$
$query$本质上也是一个类似的$pushup$

由于欧拉函数与除以二再上取整是类似的
根据此题$a_i$的值域，一个数最多经历$23$次欧拉函数就会到$1$$($可以自己打表实验$)$
所以只要按照上述思路，再套个欧拉函数的壳子即可

为什么可以递归到叶子暴力修改：
考虑一个数最多经历$20$多次欧拉函数就会到$1$这个性质
再考虑即使每次操作一都修改$[1,n]$这个最长的区间
也最多执行$20n$次，
然后$sum$就会变成$0$，之后再操作一就会及时$return$回去
对于本题也就是$2e6$次，完全可以接受

具体代码

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <bits/stdc++.h>
using ll = long long;
using PII = std::pair<int, int>;
const int N = 2e5 + 10;
const int M = 5e6 + 10;
const int K = 6;
int n, m;
int a[N];
bool is_prime[M];
int phi[M];
int prime[M];
int dep[M];
int fa[M][K];
void init_phi()
{
    for (int i = 1; i <= 5e6; i++)
        is_prime[i] = 1;
    int len = 0;
    is_prime[1] = 0;
    phi[1] = 1;
    for (int i = 2; i <= 5e6; i++)
    {
        if (is_prime[i])
        {
            prime[++len] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= len && i * prime[j] <= 5e6; j++)
        {
            is_prime[i * prime[j]] = 0;
            if (i % prime[j])
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            else
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}
void init_lca()
{
    for (int j = 1; j <= 5; ++j)
        for (int i = 1; i <= 5e6; ++i)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int get_lca(int u, int v)
{
    if (dep[u] > dep[v])
        std::swap(u, v);
    if (u == 0)
        return v;
    if (v == 0)
        return u;
    for (int i = 5; i >= 0; --i)
        if (dep[v] - dep[u] >= (1 << i))
            v = fa[v][i];
    if (u == v)
        return u;
    for (int i = 5; i >= 0; --i)
        if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}
struct Segment_Tree
{
    int lca[N * 4], sum[N * 4], ans[N * 4], len[N * 4];
    void pushup(int id)
    {
        sum[id] = sum[id << 1] + sum[id << 1 | 1];
        lca[id] = get_lca(lca[id << 1], lca[id << 1 | 1]);
        ans[id] = ans[id << 1] + ans[id << 1 | 1] + len[id << 1] * (dep[lca[id << 1]] - dep[lca[id]]) + len[id << 1 | 1] * (dep[lca[id << 1 | 1]] - dep[lca[id]]);
    }
    void build(int id, int l, int r)
    {
        len[id] = r - l + 1;
        if (l == r)
        {
            lca[id] = a[l];
            sum[id] = dep[a[l]];
            ans[id] = 0;
            return;
        }
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        pushup(id);
    }
    void modify(int id, int l, int r, int ql, int qr)
    {
        if (!sum[id])
            return;
        if (l == r)
        {
            --sum[id];
            lca[id] = fa[lca[id]][0];
            return;
        }
        int mid = l + r >> 1;
        if (qr <= mid)
            modify(id << 1, l, mid, ql, qr);
        else if (ql >= mid + 1)
            modify(id << 1 | 1, mid + 1, r, ql, qr);
        else
            modify(id << 1, l, mid, ql, mid), modify(id << 1 | 1, mid + 1, r, mid + 1, qr);
        pushup(id);
    }
    struct node
    {
        int lca, len, ans;
    };
    node query(int id, int l, int r, int ql, int qr)
    {
        if (l == ql && r == qr)
            return {lca[id], len[id], ans[id]};
        node L = {0, 0, 0}, R = {0, 0, 0}, res = {0, 0, 0};
        int mid = l + r >> 1;
        if (qr <= mid)
            L = query(id << 1, l, mid, ql, qr);
        else if (ql >= mid + 1)
            R = query(id << 1 | 1, mid + 1, r, ql, qr);
        else
            L = query(id << 1, l, mid, ql, mid), R = query(id << 1 | 1, mid + 1, r, mid + 1, qr);
        res.lca = get_lca(L.lca, R.lca);
        res.len = L.len + R.len;
        if (L.lca)
            res.ans += L.ans + L.len * (dep[L.lca] - dep[res.lca]);
        if (R.lca)
            res.ans += R.ans + R.len * (dep[R.lca] - dep[res.lca]);
        return res;
    }
};
Segment_Tree tr;
void solve()
{
    init_phi();
    for (int i = 2; i <= 5e6; ++i)
    {
        fa[i][0] = phi[i];
        dep[i] = dep[phi[i]] + 1;
    }
    init_lca();
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    tr.build(1, 1, n);
    for (int i = 1; i <= m; ++i)
    {
        int op, l, r;
        std::cin >> op >> l >> r;
        if (op == 1)
            tr.modify(1, 1, n, l, r);
        else
            std::cout << tr.query(1, 1, n, l, r).ans << '\n';
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    // std::cin >> T;
    while (T--)
        solve();
    return 0;
}