3月过完了再写3月的题解不是很正常吗

1. CF2075F

一道扫描线的题目。

题意

定义好序列为序列左右两端分别为序列唯一最小值/最大值的序列，求给定数组中最长的好序列。
数组长 \(n = 5\times 10^5\),值域 \(a \leq 10^6\).

分析

可以发现如果答案中一个数作为左端点，那么这个数左边一定没有小于等于它的数，否则我们我们选择左边小于等于它的数一定是更优的(有可能增加序列长度)。对于右端点同理，右边应该没有大于等于它的数。
称这些左端点备选点/右端点备选点为左关键点/右关键点。我们可以用单调栈\(O(n)\)预处理出这些点。这些点的规模都可以达到\(O(n)\)。
把数组元素的索引看成 \(x\),值看成 \(y\),实际上我们要求的就是左关键点作为左下，右关键点作为右上的矩形内的点数(严谨一些来说这个矩阵要缩一圈)。
于是很快可以想出来一个很暴力的\(O(n^2\log V)\)的算法：我们把左关键点和右关键点两两配对作为询问，用树状数组扫一遍离线处理(就是离线二维数点)。
但是\(O(n^2\log V)\)显然不能通过该题，而任何一对关键点确实都有成为最终答案的可能，所以我们只能想办法一次处理多个点对了。
我们可以考虑每次计算对于一个右关键点，所有左关键点的答案，取max。可以观察到对于一个点，它可以贡献到的左关键点是一个连续的区间，于是我们可以用一个线段树来维护每个左关键点的右上矩形内的点数。对于每个点的贡献区间\([l,r]\)可以\(O(n \log n)\)预处理出来。
然后就是，我们要选一个顺序\(O(n)\)加入点的贡献，同时计算出所有右关键点处，所有左关键点处答案的max(这是一个区间max操作,还是线段树即可)。
如果我们从右往左计算右关键点处的全局答案，那么用一个右关键点到下一个右关键点，矩形区域的右边界左移(删去超出边界的点)，上边界上移(加入应该加入的点)。于是我们可以想到一个加点的枚举方案：
按 \(y\) 从小到大加点，如果 \(y\) 相同则按 \(x\) 从大到小加点。如果遇到右关键点，先删去所有 \(x\)大于等于它的点的贡献，在统计一次答案。 按 \(x\) 从大到小加点的原因是我们要在加入和关键点 \(y\)坐标相同的点之前统计答案(\(x\)大于关键点的点会被删，但是\(x\)小于关键点的点还可能作为别的关键点矩形内的点，所以换个顺序枚举肯定是错误的)。
这个枚举顺序相当于两根扫描线，一根从下往上扫，一根从右往左扫，如果交点处是关键点就统计答案。
于是我们得到了一个复杂度为\(O(n\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
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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
#include<bits/stdc++.h>

using ll = long long;
using ull = unsigned long long;
using i64 = long long;
using uint = unsigned int;

using namespace std;

constexpr int inf = 1145141919;
template<class Info, class Tag> struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(vector<Info>(n_, v_));
    }
    template<class T>
    void init(vector<T> init_) {
        n = init_.size();
        info.assign(4 << (int)log2(n), Info());
        tag.assign(4 << (int)log2(n), Tag());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
            };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag& v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info& v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        }
        else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info& v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag& v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag& v) {
        return rangeApply(1, 0, n, l, r, v);
    }
    void half(int p, int l, int r) {
        if (info[p].act == 0) {
            return;
        }
        if ((info[p].min + 1) / 2 == (info[p].max + 1) / 2) {
            apply(p, { -(info[p].min + 1) / 2 });
            return;
        }
        int m = (l + r) / 2;
        push(p);
        half(2 * p, l, m);
        half(2 * p + 1, m, r);
        pull(p);
    }
    void half() {
        half(1, 0, n);
    }

    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F&& pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F&& pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F&& pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F&& pred) {
        return findLast(1, 0, n, l, r, pred);
    }

    void maintainL(int p, int l, int r, int pre) {
        if (info[p].difl > 0 && info[p].maxlowl < pre) {
            return;
        }
        if (r - l == 1) {
            info[p].max = info[p].maxlowl;
            info[p].maxl = info[p].maxr = l;
            info[p].maxlowl = info[p].maxlowr = -inf;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        maintainL(2 * p, l, m, pre);
        pre = max(pre, info[2 * p].max);
        maintainL(2 * p + 1, m, r, pre);
        pull(p);
    }
    void maintainL() {
        maintainL(1, 0, n, -1);
    }
    void maintainR(int p, int l, int r, int suf) {
        if (info[p].difr > 0 && info[p].maxlowr < suf) {
            return;
        }
        if (r - l == 1) {
            info[p].max = info[p].maxlowl;
            info[p].maxl = info[p].maxr = l;
            info[p].maxlowl = info[p].maxlowr = -inf;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        maintainR(2 * p + 1, m, r, suf);
        suf = max(suf, info[2 * p + 1].max);
        maintainR(2 * p, l, m, suf);
        pull(p);
    }
    void maintainR() {
        maintainR(1, 0, n, -1);
    }
};
struct Tag {
    int x = 0;
    void apply(const Tag& t)& {
        //x = max(x, t.x);
        x += t.x;
    }
    Tag() = default;
    Tag(int _x)
        :x(_x)
    {}
};
struct Info {
    int x = 0;

    void apply(const Tag& t)& {
        x += t.x;
    }

    Info() = default;

    Info(int _x)
        :x(_x)
    {}
};
Info operator+(const Info& a, const Info& b) {
    return { max(a.x, b.x) };

}

void solve()
{

    int n;
    cin >> n;
    vector<int>a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<int>pre, suf;

    for (int i = 1; i <= n; i++) {
        if (pre.empty() || a[i] < a[pre.back()]) {
            pre.push_back(i);
        }
    }
    for (int i = n; i >= 1; i--) {
        if (suf.empty() || a[i] > a[suf.back()]) {
            suf.push_back(i);
        }
    }
    int m = pre.size();
    vector<int>preval(m),rpreval(m);
    for (int i = 0; i < m; i++) {
        preval[i] = a[pre[i]];
        rpreval[i] = a[pre[m - 1 - i]];
    }
    vector<int>issuf(n+1);
    for (int i = 0; i < suf.size(); i++) {
        issuf[suf[i]] = 1;
    }

    LazySegmentTree<Info, Tag>t(m);
    vector<int>l(n+1), r(n+1);
    for (int i = 1; i <= n; i++) {
        l[i] = m -(lower_bound(rpreval.begin(), rpreval.end(), a[i]) - rpreval.begin()) ;
        r[i] = upper_bound(pre.begin(), pre.end(), i) - pre.begin() - 1;
    }
    vector<int>yid(n + 1);
    iota(yid.begin(), yid.end(), 0);
    sort(yid.begin(), yid.end(), [&](int i, int j)->bool
        {
            if (a[i] == a[j])return i > j;
            else return a[i] < a[j];
        });

    priority_queue<int>pq;//x
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        int id = yid[i];
        if (l[id] <= r[id]) {
            t.rangeApply(l[id], r[id] + 1, 1);
            pq.push(id);
        }
        if (issuf[id]) {
            while (!pq.empty() && pq.top() >= id) {
                int x = pq.top();
                pq.pop();
                t.rangeApply(l[x], r[x] + 1, -1);
            }
            if(l[id] <= r[id])
                ans = max(ans, t.rangeQuery(l[id], r[id] + 1).x + 2);
        }
    }
    cout << ans << endl;
    return;
    
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int tt;
    cin >> tt;
    while (tt--)
        solve();
    return 0;
}

2. CF2021E

一道kruskal重构树+树形dp，但是E3需要利用凸性优化了。

题意

一个图有\(n\)个点，\(m\)条带权边，图上有\(p\)个关键点，求图上选取\(k = 1,2,...,n\)个点作为源点时，所有关键点到任一源点的最大瓶颈路的最小值之和的最小值。
数据范围：E2 \(n,m,p \leq 5000\) , E3 \(n,m,p \leq 2\times 10^5\)

分析

E2

先看E2.
最大瓶颈路自然想到kruskal重构树算法。我们对图的最小生成树建成kruskal重构树，树上两个叶结点\(u,v\)的lca权值\(val[lca(u,v)]\)就是这两点的最小瓶颈路权值。
接下来的问题是怎么去计算题目要求的东西。
E2的数据范围足以让\(O(n^2)\)的算法通过，于是我们考虑做一个树形dp。 设置状态 \(dp[i][j]\) 表示：子树\(i\)上选择\(j\)个点作为源点时，子树上关键点的计算值的最小和,\(cnt[i]\) 表示\(i\)子树的关键点个数。
我们合并子树时，设\(u\)是\(l,r\)的父节点(kruskal重构树是一颗二叉树)，有状态转移方程：

\[\begin{align} dp[u][i] &= \min_{1\leq j\leq i-1}\{dp[l][j] + dp[r][i-j]\}\\ dp[u][i] &= \min\{cnt[l]*val[u] + dp[r][i] ,cnt[r]*val[u]+dp[l][i]\}\\ \end{align}\]

\((1)\)式实际上就是左右子树都选有点，那么左右子树内的点就不会跨过父节点(权值更大)来走最小瓶颈路了，实际上就是直接相加。
\((2)\)式描述如果一个子树内不选点，那么这个子树就要跨过父节点寻路，cost就是子树内关键点个数乘父节点(lca)权值了。
然后我们就得到了这样一个dp。
有人可能会问，这不是一眼\(O(n^3)\)?这能过\(n= 5000\)?
还真能。
实际上这是一个类似树上背包的过程，而树上背包使用了上下界优化后(dp转移几乎一致)的复杂度并非是\(O(n^3)\)，而是可以证明为是\(O(nV)\)的(\(V\)是容量限制)，证明概要是每个点对只在lca处被合并一次。所以这个dp的复杂度是\(O(np)\)，足以通过E2.
代码实现如下：

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

using ll = long long;
using ull = unsigned long long;
using i64 = long long;
using uint = unsigned int;

using namespace std;

class DSU
{
    int n;
    vector<int>fa;
    //vector<int>sz;

public:
    DSU(int n)
    {
        this->n = n;
        fa.resize(n);
        //sz.resize(n);
        for (int i = 0; i < n; i++) {
            fa[i] = i;
            //sz[i] = 1;
        }
    }

    int find(int p)
    {
        return fa[p] == p ? p : (fa[p] = find(fa[p]));
    }

    bool merge(int u, int v)
    {
        int fu = find(u), fv = find(v);
        if (fu == fv) {
            return false;
        }
        else {
            //if (sz[fu] < sz[fv]) {
            //    swap(fu, fv);
            //}
            //sz[fu] += sz[fv];
            fa[fv] = fu;
            return true;
        }
    }
};




void solve()
{
    using edge = pair<int, int>;
    using Edge = array<int, 3>;
    int n, m , k;
    cin >> n >> m >> k;
    vector<vector<edge>>g(n + 1);
    priority_queue<Edge, vector<Edge>, greater<>>pq;
    vector<int>a(k);
    for (int i = 0; i < k; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({ v,w });
        g[v].push_back({ u,w });
        pq.push({ w,u,v });
    }
    DSU dsu(n * 2);
    vector<ll>val(n * 2);
    vector<vector<int>>kruskal(n * 2);
    int id = 1;
    auto add = [&](int u, int v, int id)->void
        {
            dsu.merge(id, u);
            dsu.merge(id, v);
            kruskal[u].push_back(id);
            kruskal[v].push_back(id);
            kruskal[id].push_back(u);
            kruskal[id].push_back(v);
        };
    //kruskal
    while (id < n) {
        auto [w, u, v] = pq.top();
        pq.pop();
        if (dsu.find(u) != dsu.find(v)) {
            val[n + id] = w;
            int a = dsu.find(u), b = dsu.find(v);
            add(a, b, n + id);
            id++;
        }
    }

    vector<int>cnt(n * 2);
    for (auto p : a) {
        cnt[p]++;
    }
    constexpr ll inf = 1e16 + 10;
    auto dfs = [&](auto&& self, int p, int fa)->vector<ll>
        {
            if (kruskal[p].size() == 1) {
                vector<ll>dp(2);
                dp[0] = cnt[p] ? inf : 0;
                dp[1] = 0;
                return dp;
            }
            else {
                array<vector<ll>, 2>sdp;
                array<int, 2>sons;
                int id = 0;
                for (auto s : kruskal[p]) {
                    if (s != fa) {
                        sons[id] = s;
                        sdp[id++] = self(self, s, p);
                    }
                }
                auto& [l, r] = sdp;
                auto& [L, R] = sons;
                cnt[p] = cnt[L] + cnt[R];
                vector<ll>dp(l.size() + r.size() - 1, inf);
                for (int i = 1; i < l.size(); i++) {
                    for (int j = 1; j < r.size(); j++) {
                        dp[i + j] = min(dp[i + j], l[i] + r[j]);
                    }
                }
                
                for (int i = 1; i < l.size(); i++) {
                    dp[i] = min(dp[i], l[i] + val[p] * cnt[R]);
                }
                for (int j = 1; j < r.size(); j++) {
                    dp[j] = min(dp[j], r[j] + val[p] * cnt[L]);
                }
                return dp;
            }
        };

    auto &&dp = dfs(dfs, n * 2 - 1, 0);
    for (int i = 1; i <= n; i++) {
        cout << dp[i] << " ";
    }
    cout << endl;
    return;

}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int tt;
    cin >> tt;
    while (tt--)
        solve();
    return 0;
}

E3

E3 的数据范围为\(2\times 10^5\),\(O(np)\)的算法显然无法通过了，我们只能去寻求\(O(n\log n)\)的做法。
我们的求解的方法(树形dp)显然没办法被替换成别的办法了，但是dp的均摊转移时间是\(O(p)\)的，我们或许可以想办法优化dp转移。
再观察dp转移式：

\[\begin{align*} dp[u][i] &= \min_{1\leq j\leq i-1}\{dp[l][j] + dp[r][i-j]\}\\ dp[u][i] &= \min\{cnt[l]*val[u] + dp[r][i] ,cnt[r]*val[u]+dp[l][i]\}\\ \end{align*}\]

可以发现\((1)\)式是一个{min,+}卷积的形式，这或许是在提示我们往凸优化的方向去想。再想一想\(dp[i]\)这个函数，可以发现它的差分是单调递减的(非严格)，因为如果我们选取第\(i\)个点后减小\(d_i\)，选取第\(i+1\)个点后减小\(d_{i+1}\),如果\(d_i < d_{i+1}\)，那么我们显然可以交换这两次选的点使得\(d_i\)更小，这是违背dp状态定义的。所以\(dp[i]\)是一个下凸的函数。
现在我们知道了这个函数是下凸的，那么{min,+}卷积就可以用闵可夫斯基和做，实际上就是维护两个凸包的差分序列，贪心加入更大值。
那么合并这个差分数组，我们就可得到\(dp[i]\)从\(1\)开始的向后差分，但是\(0\)对\(1\)的差分不太符合。
我们合并两个凸包时，都加入了子树内\(dp[i][0] - dp[i][1]\)的值，但是这个值在向上转移时\(dp[i][0]\)的代价发生了变化。因此我们应该进行一些修改。
考虑\(0\)对\(1\)的差分，这对应的是不选其中一颗子树时的特殊转移。根据dp数组的定义，这是选择其中一颗子树的一个点时，最小的权值和。
写出选择\(l\)子树的差分值：

\[\begin{align*} d_1(u)_l &= cnt[p]*val[p] - (cnt[r] *val[p] + dp[l][1]) \\ &= (cnt[p] - cnt[r])*val[p] -(cnt[l]*val[l] - d_1(l)) \\ &= cnt[l]*(val[p]-val[l]) + d_1(l) \end{align*}\]

选择\(r\)子树的差分值类似。
我们要做的就是把\(d_1(l)\)和\(d_1(r)\)换成这个式子即可。
当然也有难以理解一些的做法：
可以发现这是仅和\(l\)或\(r\)及其父亲相关的一个式子。
那么我们其实可以直接在转移到父亲的时候就把这个式子换成父亲的式子(就是\(d_1(p) \rightarrow d_1(fa[p])_p\)),特判一下根处不做这个操作即可。
这样，我们就把一次转移优化到了\(O(size(p))\),而对于这样的树上转移和合并，我们有强大的武器：树上启发式合并来维护差分序列的转移，这样整个转移我们可以实现到\(O(n\log n)\)。如果我们使用multiset维护差分序列，最终的复杂度是\(O(n^2\log n)\).
得到差分序列，我们可以反向还原出\(k = 1,2,...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
89
90
91
92
93
94
95
96
97
98
void solve()
{
//...
//前面与E2保持一致    
    vector<int>cnt(n * 2);
    for (auto p : a) {
        cnt[p]++;
    }
    //预处理启发式合并
    const int root = n * 2 - 1;
    vector<int>hson(n * 2);
    vector<int>lson(n * 2);
    auto get_hson = [&](auto&& self, int p, int fa)->void
        {
            for (auto s : kruskal[p]) {
                if (s != fa) {
                    self(self, s, p);
                    cnt[p] += cnt[s];
                    if (hson[p] == 0 || cnt[hson[p]] < cnt[s]) {
                        lson[p] = hson[p];//don't forget
                        hson[p] = s;
                    }
                    else {
                        lson[p] = s;
                    }
                }
            }
        };
    get_hson(get_hson, root, 0);
    constexpr ll inf = 1e16 + 10;
    ll sum = 0;
    multiset<ll>d;

    //实现1
    auto dfs = [&](auto&& self, int p, int fa, multiset<ll>& d)->void
    {
        if (kruskal[p].size() == 0) {
            if (cnt[p]) {
                d.insert(0);
            }
        }
        else {
            multiset<ll>r;
            self(self, hson[p], p, d);
            self(self, lson[p], p, r);
            if (!d.empty()) {
                auto x = prev(d.end());
                d.insert((val[p] - val[hson[p]]) * cnt[hson[p]] + *x);
                d.erase(x);
            }
            if (!r.empty()) {
                for (auto iter = r.begin(); next(iter) != r.end(); iter++) {
                    d.insert(*iter);
                }
                auto y = prev(r.end());
                d.insert((val[p] - val[lson[p]]) * cnt[lson[p]] + *y);
            }
        }
    };

    //实现2
    auto dfs = [&](auto&& self, int p, int fa, multiset<ll>&d)->void
        {
            if (kruskal[p].size() == 0) {
                if (cnt[p]) {
                    d.insert(val[fa]);
                }
            }
            else {
                multiset<ll>r;
                self(self, hson[p], p, d);
                self(self, lson[p], p, r);
                for (auto v : r) {
                    d.insert(v);
                }
                if (!d.empty() && p != root) {//modify dp[0]
                    auto x = prev(d.end());
                    d.insert(*x + (val[fa] - val[p]) * cnt[p]);
                    d.erase(x);
                }
            }
        };

    dfs(dfs, root, 0, d);
    vector<ll>ans(n + 1);
    ans[0] = val[root] * cnt[root];
    id = 1;
    //从大到小遍历
    for (auto rit = d.rbegin(); rit != d.rend();rit++) {
        ans[id++] =  ans[id - 1] - *rit;
    }
    ans.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
    return;
}
然而，从哥哥那里学到了更好的写法 
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
constexpr ll inf = 1e16 + 10;
    ll sum = 0;
    vector<ll>d;
    auto dfs = [&](auto&& self, int p, int fa)->ll
        {
            if (kruskal[p].size() == 0) {
                if (cnt[p]) {
                    return val[fa];
                }
                else {
                    return 0;
                }
            }
            else {
                ll vl = 0, vr = 0;
                vl = self(self, hson[p], p);
                vr = self(self, lson[p], p);
                if (vl < vr)swap(vl, vr);
                d.push_back(vr);
                if (p != root) {//modify dp[0]
                    vl += ((val[fa] - val[p]) * cnt[p]);
                }
                return vl;
            }
        };

    d.push_back(dfs(dfs, root, 0));//jiangly 维护 max 的方法太优雅了
    sort(d.begin(), d.end(), greater<>());
    vector<ll>ans(n + 1);
    ans[0] = val[root] * cnt[root];
    id = 1;
    for (auto v : d) {
        ans[id++] = ans[id - 1] - v;
    }
    ans.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
jiangly使用了类似实现2的维护差分序列的方式。
由于我们只需要修改\(d_1\),即差分序列最大值，其他值绝对不变，前面我们使用multiset加启发式合并是没有必要的。
我们还是选择dfs，返回\(d_1(fa[p])_p\),每个非叶节点接受两个返回值后，存入那个较小的,修改那个较大的为对应返回值(根节点除外)后返回。 这样的话，我们就无需在dfs过程中存储维护差分序列，而是每次将不再会修改的值加入全局的差分序列中即可。最后再排个序。时间复杂度为\(O(n\log n)\)。(哥哥还是太强了!要多学习哥哥代码!)。

3. CF2089B2

很典的破链成环的题。
本来想写个破链成环的专题的，但是想着手上也就两三道就算了，在这里提一嘴得了

题意

大致上\(a,b\)两个数组，\(\operatorname{sum}(a) \leq \operatorname{sum}(b)\),\(a\)每次减去对应位置的\(b\)直到\(a\)等于\(0\)，操作完循环右移一位再次操作，问多少次操作可以把\(a\)全部置为0。
B2的附加条件是可以初始对\(a\)任意位置元素进行最多\(k\)次递减操作。
数据范围：数组长\(n \leq 2\times 10 ^ 5\)

分析

首先把链展开为\(2n\)的链，在链上滑动窗口一下，记录每个\(a\)的和小于等于\(b\)的和的子段长，最大值即为答案。
这样B1就写完了。
有一说一，一开始看到这个还以为要二分，后面发现直接求就可以。
再说B2。
B2被yzc在群里说什么优先队列维护位置什么的误导了，想不懂他是怎么维护的，搞得我以为B2很神秘，后面发现完全不用那样。
对于k，我们直接二分答案即可。(没错，B1我想过的二分在这里回来了，我居然没想出来，QAQ).
check的方法也不难，我们找到B1解法中，最长段的左端点\(l\)(如果有多个，选最左边那个)。可以证明这个左端点\(l\)小于等于\(n\)。
然后我们再在\([l,l+n)\)这个区间上跑一个滑动窗口，每次加入\(a\)，用\(b\)一直减队尾的\(a\)，如果队首的\(a\)超出了我们check的轮数就用k次递减减去。而最后肯定消完了，不用考虑剩下的(这就是我们选择\(l\)作为区间左端点的理由)。
代码实现：

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

using ll = long long;
using ull = unsigned long long;
using i64 = long long;
using uint = unsigned int;

using namespace std;


void solve()
{
    ll n, k;
    cin >> n >> k;
    vector<ll>a(n*2), b(n*2);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        b[i + n] = b[i];
    }
    int l = 0;
    ll sa = 0, sb = 0;
    int len = 0;
    int ans = 0;
    for (int i = 0; i < n * 2; i++) {
        sa += a[i];
        sb += b[i];
        len++;
        if (sa <= sb) {
            sa = 0;
            sb = 0;
            if (len > ans) {
                l = i - len + 1;
            }
            ans = max(ans, len);
            len = 0;
        }
    }

    auto check = [&](int rounds) ->bool
        {
            ll rem = k;
            int pa = l, pb = l;
            deque<pair<int,ll>>qa;
            for (int i = l; i < l + n; i++) {
                qa.push_back({ i,a[i] });
                if (!qa.empty() && i - qa.front().first == rounds) {
                    rem -= qa.front().second;
                    qa.pop_front();
                }
                ll x = b[i];
                while (!qa.empty() && x != 0) {
                    if (x < qa.back().second) {
                        qa.back().second -= x;
                        x = 0;
                    }
                    else {
                        x -= qa.back().second;
                        qa.pop_back();
                    }
                }
            }
            return rem >= 0;
        };

    int L = -1, R = ans;
    while (R - L > 1) {
        int m = L + R >> 1;
        if (check(m)) {
            R = m;
        }
        else {
            L = m;
        }
    }
    cout << R << endl;
    return;

}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int tt;
    cin >> tt;
    while (tt--)
        solve();
    return 0;
}

4. CF2085F2

带点思维的题，一开始没想到用初始状态和最终状态确定贡献的算法，想了一下午一晚上。

题意

定义好数组为长为\(k\)且\(1 \sim k\)均出现一次的数组。给一个长度为\(n\)的数组\(a\)，只能相邻两两交换，问最少操作多少次使得有一个子数组是好数组。保证\(a\)中\(1\sim k\)至少出现一次。
数据范围：F1 \(k\leq n\leq 3000\), F2 \(k \leq n\leq 4\times 10^5\)

分析

F1允许\(O(n^2 \log n)\)通过，F2则至少要\(O(n \log n)\).
先想想我们移动的策略：我们假设最终组成好数组的是一些元素，那么最优操作是把两边的元素往中间的元素交换靠拢。
假设中间元素的位置是 \(x\)，\(l = \left\lfloor\frac{k}{2}\right\rfloor, r = \left\lceil\frac{k}{2}\right\rceil\)，选中元素的初始位置是\(pos(i)\)
那么可以用操作花费可以用一个公式描述
\[cost(x) = \sum_{i = 1}^k \left| x - pos(i)\right| - \frac{l(l+1)}{2} - \frac{r(r+1)}{2}\] (对于一些位置，这个公式的计算结果是不对的，因为不能均匀从两边靠拢。但是我们可以证明中间位置的计算结果永远会比这些不正确的结果不劣，所以没影响)
我们可以对于每个位置\(x\)，遍历一遍数组，计算每个位置的值并放到对应元素值处，每个元素值取最小结果，最后计算这个式子即可得到答案。 计算这个式子的时间复杂度为\(O(n)\),所以我们得到了一个\(O(n^2)\)的F1做法。

对于F2,对每个位置重新计算一次\(cost\)显然没有利用好上一次计算的信息。
我们先对\(k\)个值的每个值单独考虑，可以把每个元素的贡献写成一张\(n \times k\)的数表。
示例：

实际上cost就是不同值的cost的叠加。
可以观察到同一值相邻的cost只有3种变化\(\{-1,0,1\}\),那么我们使用差分来研究它们的性质，这里取向前差分
设\(d_1(i) = cost(i) - cost(i-1)\)，我们抽出上面例子中的值\(1\)来研究，无关值用\(0\)代替

可以观察到，\(d_2\)在每个值出现位置加一处取2(一阶差分从-1跳变到1)，同时两个相同值的中间两个位置加一处各减一。
根据这个规律，我们\(O(n)\)预处理出\(d_2\),再还原出\(d_1,cost\)，再遍历\(cost\)取得最大答案即可。
最后时间复杂度为\(O(n)\)，很神奇。