【CF1051G】 Distinctification 题解

pldzy · 2022-08-02 12:03:50 · 题解

~~很感谢这道花费了我一整个上午的题目，很感谢。~~

CF 传送门

线段树合并 + 并查集维护。

Update

2023.03.15：题意描述的图炸了，修图。

Description

题意概述。

Solution

以下使用 a_i 代替 A_i，b_i 同理。

1 观察

观察这两个操作，容易发现如果新加进来一个数，想要通过操作这个数使得序列中没有重复的数，只能是把这个新数不断加一直到没有数与它相同。通过这个观察，可以得到结论：最终 a_i 构成的集合是确定的。注意，是集合确定。

进一步观察这两个操作，就能发现：对于 1\leq i,\ j \leq n，若 a_i = a_j + 1，可以通过花费 b_j-b_i 的代价，将两者交换。交换有什么好处？若 b_i < b_j，则 a_i \times b_i + a_j \times b_j \geq a_i \times b_j + a_j \times b_i。

同时，不妨假设最后满足条件的整个操作后序列每项为 c_i,\ 1\leq i \leq n。那么总共所需代价即为 \sum_{i=1}^n (c_i-a_i) \times b_i。为什么？因为若 a_i 加了 1，代表花费增加了 b_i；若 a_i 减去 1，代表花费减少了 b_i。那么最后 a_i 总共增加了 (c_i-a_i)，但是内部过程是如何的我们实际上并不会关注，因为除了 (c_i-a_i) \times b_i 之外 a_i 带来的花费已经抵消掉了。故最终的花费总共为 \sum_{i=1}^n (c_i-a_i) \times b_i。进一步拆分，得总代价为 \sum_{i=1}^n c_i \times b_i - \sum_{i=1}^na_i \times b_i，而式子中的第二项已经确定，所以我们想要 c_i\times b_i 的总和尽可能小。

综上两段分析，我们明白：我们需要做的是通过交换 a 中元素的位置，即重新排序使得答案最小。

因为交换 a_i 和 a_j 的前提条件是 a_i=a_j+1，故我们只能在⼀个 a_i 的连续段内任意调整顺序。为了不破坏连续段的单调递增性，我们将调换 a_i 的顺序转化为调换 b_i 的顺序，这并不影响结果。再结合交换两项带来的优势，不难得出：我们要在一个 a 的连续段内将其相对应的 b 中的项从大到小排序，然后与 a 中的项一一对应，从而达到 \sum_{i=1}^n c_i\times b_i 尽可能小的目的。

2 求每个连续段花费

为了维护连续段并且支持合并（加入新的数），我们考虑线段树合并。rt_i 表示段内最小的数为 i 的连续段（此时已保证 a_i 两两互不相同）相对应的一棵权值线段树。线段树内部以 b_i 为下标。

显然，在 rt_i 这棵权值线段树内，每个 b_i 从小到大排好了序。而我们要求的，就是这些 b_i 从大到小分别乘上对应最小值为 i 的从小到大的连续段的每一项。我们可以明确一点：每个 b_i 都会至少乘上 i，故可以直接将 t_{rt_i}.sum \times i 统计进 ans，之后加入每个 b_i（b_i 从小到大升序排列）乘上 a 中第 t_{rt_i}.size - i + 1 项的两者之积。

那怎么快速求得这些乘积的和呢？其实只需要在递归线段树的时候，每一层都给 ans 加上 t_{ls}.sum \times t_{rs}.siz 即可。可以感性理解为每一层都将 [l,mid] 和 [mid+1,r] 这两个区间调换了位置，那最后整个 b 序列肯定被排为从大到小的降序排列。而上面的 t_{ls}.sum \times t_{rs}.siz 就是将区间 [l,mid] 移位到了区间 [mid+1,r] 之后所多出的花费。

3 统计加数后答案

知道如何统计每个连续段的贡献之后，分析一下每次新加入一个数之后如何重新统计答案。流程如下：

找到输入的这个数 a_i 所在的连续段中，最大的数是多少。而 a_i，就要赋值为这个最大值加一的数，记为 y。
统计将 a_i 变为 y 所需的代价，加进 ans。此代价即为 (y-a_i)\times b_i。
将 rt_y 与左右相邻的段的权值线段树合并（前提是要合并段不为空），左右相邻的连续段即为 rt_{y-1} 和 rt_{y+1}。
合并时已经重新统计过新的连续段的代价，故此时直接输出答案即可。

并查集维护什么？当然就是第一步中每个数所在的连续段的最小值（即左端点），同时再开一个数组维护相应右端点即可。

为了保证不重复，每个 a_i 都要加 1 加到不与之前数重复，所以极端情况下 a_i 可能加到 2 \times 2e5，故数组要开两倍。

至此，该题已彻底解决，时复 O(n \log n)。

Code

#include<bits/stdc++.h>
using namespace std;

#define ll long long 
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
const int maxn = 4e5 + 10, maxm = maxn * 30;
int n, rt[maxn], fa[maxn], bl[maxn];
ll ans;

inline int fnd(int x){
    return x == fa[x] ? x : fa[x] = fnd(fa[x]);
}

struct segment_tree{
    #define L(x) ch[0][x]
    #define R(x) ch[1][x]
    #define ls L(x)
    #define rs R(x)
    #define sz(x) t[x].siz
    #define sm(x) t[x].sum
    struct tree{
        int siz; ll sum;
    }t[maxm]; int tot, ch[2][maxm];
    inline void up(int x){
        sm(x) = sm(ls) + sm(rs), sz(x) = sz(ls) + sz(rs);
    }
    inline void updt(int &x, int l, int r, int p){
        if(!x) x = ++tot;
        if(l == r){
            sz(x) = 1, sm(x) = p; return;
        } int mid = l + r >> 1;
        p <= mid ? updt(ls, l, mid, p) : updt(rs, mid + 1, r, p);
        up(x);
    }
    inline int merge(int a, int b, int l, int r){
        if(!a or !b) return a + b;
        int x = ++tot; if(l == r) return x;
        ans -= sm(L(a)) * sz(R(a)) + sm(L(b)) * sz(R(b));
        int mid = l + r >> 1;
        ls = merge(L(a), L(b), l, mid), rs = merge(R(a), R(b), mid + 1, r);
        ans += sm(ls) * sz(rs), up(x); return x;
    }
    inline void link(int a, int b){
        a = fnd(a), b = fnd(b), fa[b] = a;
        ans -= sm(rt[a]) * a + sm(rt[b]) * b;
        rt[a] = merge(rt[a], rt[b], 1, n);
        ans += sm(rt[a]) * a, bl[a] = bl[b];
    }
}T;

int main(){ rep(i, 1, maxn - 5) fa[i] = bl[i] = i;
    scanf("%d", &n); 
    rep(i, 1, n){ int x, y, v;
        scanf("%d%d", &x, &v);
        y = rt[x] ? bl[fnd(x)] + 1 : x;
        ans += 1ll * (y - x) * v;
        T.updt(rt[y], 1, n, v);
        if(rt[y - 1]) T.link(y - 1, y); if(rt[y + 1]) T.link(y, y + 1);
        printf("%lld\n", ans);
    }
    return 0;
}

感谢阅读。