【CF1051G】 Distinctification 题解

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

CF 传送门

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

Description

Solution

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

1 观察

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

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

同时，不妨假设最后满足条件的整个操作后序列每项为 $c_i,1\le i\le 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}^n{a}_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 求每个连续段花费

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

显然，在 $r{t}_i$ 这棵权值线段树内，每个 $b_i$ 从小到大排好了序。而我们要求的，就是这些 $b_i$ 从大到小 分别乘上 对应最小值为 $i$ 的从小到大的连续段的每一项。我们可以明确一点：每个 $b_i$ 都会至少乘上 $i$，故可以直接将 $t_{r{t}_i}.sum\times i$ 统计进 $ans$，之后加入每个 $b_i$（$b_i$ 从小到大升序排列）乘上 $a$ 中第 $t_{r{t}_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 统计加数后答案

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

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

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

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

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

Code

#include
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;
}
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

---

感谢阅读。