一个长度为 nn 序列, 每个位置有 ai,bia_i, b_i 两个参数,且bib_i 互不相同, 你可以进行任意次如下的两种操作:

  1. 若存在 j≠ij \neq i 满足 aj=aia_j = a_i, 则可以花费 bib_i 的代价令 aia_i 加一.
  2. 若存在 jj 满足 aj+1=aia_j + 1 = a_i, 则可以花费 −bi-b_i 的代价令 aia_i 减一.

定义一个序列的权值为将序列中所有 aia_i 变得互不相同所需的最小代价.求给定序列的每一个前缀的权值.

n,ai≤2×105,1≤bi≤nn, a_i \le 2 \times 10^5, 1 \le b_i \le n

CF 1051G

Solution

考虑所有 aia_i 互不相同的时候怎么做

若存在 ai+1=aja_i + 1 = a_j, 则可以花费 bi−bjb_i-b_j 的代价交换两个 aia_i. 显然最优方案会将序列中所有 aia_i 连续的子段操作成按 bib_i 降序的.

如果有 aia_i 相同, 则可以先将所有 aia_i 变成互不相同的再进行排序, 但是这时可能会扩大值域使得原本不连续的两个区间合并到一起,于是我们需要维护一个支持合并的数据结构.

我们用并查集维护每个值域连续的块,并在每个并查集的根上维护一个以 bb 为关键字的值域线段树,每次合并两个联通块时, 合并他们对应的线段树即可维护答案.

考虑如何具体维护线段树

可以发现某个前缀的答案就是最终aibia_ib_i的前缀和减去一开始的aibia_ib_i的前缀和

因为不管中间如何变化,对于每一个ii,它最终的贡献一定是(anew−aold)∗bi(a_{new}- a_{old}) * b_i

一开始的前缀和可以直接前缀和统计,那么我们就只需要维护不断变化的∑aibi\sum{a_ib_i}

并且因为aia_i是连续的,可以假设aia_i都是从1开始的,最后答案再加上(ai−1)∗sum(a_i - 1) * sum

因此线段树里只需要统计每个值乘比它大的数的个数

某个节点的答案就是左右子树的答案和加上左子树的sumsum乘上右子树的sizesize

总体来说这道题前面一部分还是比较好理解的,具体维护线段树这里搞了好久才搞懂

Code

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

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
inline int read ()
{
	int sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 4e5 + 100;

int N, A[Maxn], B[Maxn], Root[Maxn];
LL Sum[Maxn], ans;

struct tree
{
	int ch[2], size;
/**/LL sum, val;
}Tree[Maxn * 30];

namespace SEG
{
#define ls Tree[Tree[root].ch[0]]
#define rs Tree[Tree[root].ch[1]]
#define lson Tree[root].ch[0], l, mid
#define rson Tree[root].ch[1], mid + 1, r

	int node_cnt;

	inline void push_up (int root)
	{
		Tree[root].sum = ls.sum + rs.sum;
		Tree[root].size = ls.size + rs.size;
		Tree[root].val = ls.val + rs.val + 1ll * ls.sum * rs.size;
	}

	inline void build (int &root, int l, int r, int x)
	{
		if (!root) root = ++node_cnt;
		if (l == r)
		{
			Tree[root].sum = Tree[root].val = x, Tree[root].size = 1;
			return ;
		}
		int mid = l + r >> 1;
		if (x <= mid) build (lson, x);
		else build (rson, x);
		push_up (root);
	}

	inline int merge (int x, int y)
	{
		if (!x || !y) return x | y;
		int now = x;
		Tree[now].ch[0] = merge (Tree[x].ch[0], Tree[y].ch[0]);
		Tree[now].ch[1] = merge (Tree[x].ch[1], Tree[y].ch[1]);
		if (!Tree[now].ch[0] && !Tree[now].ch[1])
		{
			Tree[now].val = Tree[x].val + Tree[y].val + 1ll * Tree[y].sum * Tree[x].size;
			Tree[now].sum = Tree[x].sum + Tree[y].sum;
			Tree[now].size = Tree[x].size + Tree[y].size;
		}
		else push_up (now);
		return now;
	}

	LL query (int x) { return Tree[Root[x]].val + 1ll * (x - 1) * Tree[Root[x]].sum; }
#undef lson
#undef rson
#undef ls
#undef rs
}

namespace DSU
{
	int fa[Maxn];
	inline void init (int maxn) { for (int i = 1; i <= maxn; ++i) fa[i] = i; }
	inline int find (int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
	inline void link (int x, int y)
	{
		int fx = find(x), fy = find(y);
		fa[fy] = fx;
		ans -= SEG :: query (fx) + SEG :: query (fy);
		Root[fx] = SEG :: merge (Root[fx], Root[fy]);
		ans += SEG :: query (fx);
	}
}

inline void Input ()
{
	N = read();
	DSU :: init(4e5);
	for (int i = 1; i <= N; ++i)
	{
		A[i] = read(), B[i] = read();
		Sum[i] = Sum[i - 1] + 1ll * A[i] * B[i];
		A[i] = DSU :: find(A[i]), DSU :: fa[A[i]] = A[i] + 1;
		SEG :: build (Root[A[i]], 1, (int)(4e5), B[i]);
	}
}

int Vis[Maxn];

inline void Solve ()
{
	DSU :: init(4e5);
	for (int i = 1; i <= N; ++i)
	{
		ans += SEG :: query (A[i]);
		if (Vis[A[i] + 1]) DSU :: link (A[i], A[i] + 1);
		if (Vis[A[i] - 1]) DSU :: link (A[i] - 1, A[i]);
		Vis[A[i]] = 1;
		printf("%lld\n", ans - Sum[i]);
	}
}

int main()
{
#ifdef hk_cnyali
	freopen("G.in", "r", stdin);
	freopen("G.out", "w", stdout);
#endif
	Input();
	Solve();
	return 0;
}

Debug

  • 33L: sum和val要开long long