CF1051G Distinctification

Day \(3^3\)。

未卡常拿到了最优解/cy。（2023/10/2）

观察到 \(3\) 个比较关键的性质：

• 操作具有可逆性，即一串操作序列可以立即撤销。
• 当新插入一个 \((a_i,b_i)\) 时，必须连续对 \(i\) 进行 \(1\) 操作使得不存在 \(j\neq i,a_j=a_i\)。
• 当存在 \(a_i=a_j+1\) 时，可以花费 \(b_j-b_i\) 的代价交换 \(a_i\) 和 \(a_j\)，如果 \(b_j<b_i\)，交换 \(a_i,a_j\) 一定更优。

所以考虑最后的 \(a_i\) 在值域上形成的连续段，贪心策略是使每个连续段的 \(b_i\) 递减。而由于插入一个 \((a_i,b_i)\) 时，先将 \(a_i\) 移动到其所在连续段的末尾，然后只需要考虑合并两个连续段，所以连续段数量变化为 \(O(1)\)，考虑数据结构维护每个连续段的 \(b\) 的信息。

首先可以用并查集维护出某个 \(a_i\) 所在的连续段的右端点。然后在每个连续段的右端点上维护一棵以 \(b\) 为下标的权值线段树，线段树节点 \(x\) 代表区间 \([l,r]\) 记录这个连续段内 \(c_{x,l,r}=\sum\limits[b_i\in [l,r]]\) 和 \(s_{x,l,r}=\sum\limits b_i[b_i\in [l,r]]\) 的值。

合并两个连续段 \(x,y\)（\(l_y>r_x\)） 时，先将 \(y\) 左端点和 \(x\) 对齐（即目前答案减去 \(c_{x,1,n}\cdot s_{y,1,n}\)）。然后只需要考虑将 \(x,y\) 中所有元素重排后的最小答案，根据贪心策略进行线段树合并并且计算贡献，类似 cdq 分治，每次考虑 \(i\in x,j\in y\) 或者 \(i\in y,j\in x\) 满足 \(b_i\le \text{mid}< b_j\) 的 \(b_i\) 跨过 \(b_j\) 所产生的贡献即可，为 \(s_{x,l,\text{mid}}\cdot c_{y,\text{mid+1},r}\)。

// Problem: Distinctification
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1051G
// Memory Limit: 500 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;

const int N = 4e5 + 400;

ll ans;
int n, cnt, fa[N], rt[N];
struct seg { int lc, rc, cnt; ll sum; } tr[N << 5];
int gf(int x) { return x == fa[x] ? x : fa[x] = gf(fa[x]); }

#define ls tr[x].lc
#define rs tr[x].rc
#define mid ((l + r) >> 1)

void upd(int l, int r, int p, int &x) {
	if (!x) x = ++cnt;
	tr[x].cnt++, tr[x].sum += p;
	if (l == r) return;
	if (p <= mid) upd(l, mid, p, ls);
	else upd(mid + 1, r, p, rs);
}

void mrg(int l, int r, int &x, int y) {
	if (!x || !y) return x = (x | y), void();
	ans += tr[ls].sum * tr[tr[y].rc].cnt + tr[rs].cnt * tr[tr[y].lc].sum;
	if (l == r) return tr[x].sum += tr[y].sum, tr[x].cnt += tr[y].cnt, void();
	mrg(l, mid, ls, tr[y].lc), mrg(mid + 1, r, rs, tr[y].rc);
	tr[x].sum = tr[ls].sum + tr[rs].sum, tr[x].cnt = tr[ls].cnt + tr[rs].cnt;
}

void calc(int x, int y) {
	x = gf(x), y = gf(y);
	fa[x] = y, ans -= tr[rt[x]].cnt * tr[rt[y]].sum;
	mrg(1, n, rt[y], rt[x]);
}

void solve() {
	cin >> n;
	for (int i = 1; i <= 4e5; i++) fa[i] = i;
	for (int i = 1, x, y; i <= n; i++) {
		cin >> x >> y;
		if (rt[x]) {
			int r = gf(x) + 1;
			ans += 1ll * (r - x) * y, x = r;
		}
		upd(1, n, y, rt[x]);
		if (rt[x - 1]) calc(x - 1, x);
		if (rt[x + 1]) calc(x, x + 1);
		cout << ans << '\n';
	}
}

bool Med;
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
	#ifdef FILE
		freopen("1.in", "r", stdin);
		freopen("1.out", "w", stdout);
	#endif
	int T = 1;
	// cin >> T;
	while (T--) solve();
	cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
	return 0;
}