CF1051G Distinctification()

记原序列从 \(a_{1\cdots n}\) 变成 \(s_{1\cdots n}\) 最终的答案应该是

观察得这个东西与交换的过程无关，所以我们只需要关注如何找到最终的结果。

如果存在 \(i,j\) 使得 \(a_i-a_j=1\)，那么交换它们，所用的代价是 \(b_j-b_i\)。

考虑最终的序列，如果有一段满足 \(a\) 值连续，那么这一段一定可以互相交换。而分析答案的式子，知道对于一个 \(a\) 的连续段，让 \(b\) 降序应该最优。

值域段需要合并，这里用并查集。

合并的同时需要维护答案，所以使用线段树合并。

#import<stdio.h>
#import<numeric>
#import<algorithm>
using namespace std;

using ll = long long;

const int N = 4e5 + 5;
const int S = N * 25;

int n,a[N],b[N],c[N],fa[N],rt[N]; ll res; bool vis[N];

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

int lc[S],rc[S],siz[S],tot; ll sum[S],val[S];
#define mid ((L + R) >> 1)

void psu(int i,int ls,int rs){
	siz[i] = siz[ls] + siz[rs];
	sum[i] = sum[ls] + sum[rs];
	val[i] = val[ls] + val[rs];
	val[i] += sum[ls] * siz[rs];
}

void ins(int x,int &i,int L = 1,int R = 2e5){
	if(!i) i = ++tot;
	if(L == R) return sum[i] = val[i] = x,void(siz[i] = 1);
	x <= mid ? ins(x,lc[i],L,mid) : ins(x,rc[i],mid + 1,R);
	psu(i,lc[i],rc[i]);
}

int mrg(int x,int y){
	if(!x || !y) return x + y; int i = x;
	lc[i] = mrg(lc[x],lc[y]);
	rc[i] = mrg(rc[x],rc[y]);
	(lc[i] || rc[i]) ? psu(i,lc[i],rc[i]) : psu(i,y,x);
	return i;
}

ll cnt(int i){ return sum[rt[i]] * (i - 1) + val[rt[i]]; };

void upd(int x,int y){
	fa[y = fnd(y)] = x = fnd(x);
	res -= cnt(x) + cnt(y);
	rt[x] = mrg(rt[x],rt[y]);
	res += cnt(x);
}

signed main(){
	scanf("%d",&n);
	iota(begin(fa),end(fa),0);
	for(int i = 1;i <= n;++i){
		scanf("%d%d",a + i,b + i);
		c[i] = fnd(a[i]);
		fa[c[i]] = c[i] + 1;
		ins(b[i],rt[c[i]]);
	}
	iota(begin(fa),end(fa),0);
	ll sum = 0;
	for(int i = 1;i <= n;++i){
		res += cnt(c[i]);
		if(vis[c[i] + 1]) upd(c[i],c[i] + 1);
		if(vis[c[i] - 1]) upd(c[i] - 1,c[i]);
		sum += 1LL * a[i] * b[i];
		vis[c[i]] = true;
		printf("%lld\n",res - sum);
	}
	return 0;
}
————————

记原序列从 \(a_{1\cdots n}\) 变成 \(s_{1\cdots n}\) 最终的答案应该是

观察得这个东西与交换的过程无关，所以我们只需要关注如何找到最终的结果。

如果存在 \(i,j\) 使得 \(a_i-a_j=1\)，那么交换它们，所用的代价是 \(b_j-b_i\)。

考虑最终的序列，如果有一段满足 \(a\) 值连续，那么这一段一定可以互相交换。而分析答案的式子，知道对于一个 \(a\) 的连续段，让 \(b\) 降序应该最优。

值域段需要合并，这里用并查集。

合并的同时需要维护答案，所以使用线段树合并。

#import<stdio.h>
#import<numeric>
#import<algorithm>
using namespace std;

using ll = long long;

const int N = 4e5 + 5;
const int S = N * 25;

int n,a[N],b[N],c[N],fa[N],rt[N]; ll res; bool vis[N];

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

int lc[S],rc[S],siz[S],tot; ll sum[S],val[S];
#define mid ((L + R) >> 1)

void psu(int i,int ls,int rs){
	siz[i] = siz[ls] + siz[rs];
	sum[i] = sum[ls] + sum[rs];
	val[i] = val[ls] + val[rs];
	val[i] += sum[ls] * siz[rs];
}

void ins(int x,int &i,int L = 1,int R = 2e5){
	if(!i) i = ++tot;
	if(L == R) return sum[i] = val[i] = x,void(siz[i] = 1);
	x <= mid ? ins(x,lc[i],L,mid) : ins(x,rc[i],mid + 1,R);
	psu(i,lc[i],rc[i]);
}

int mrg(int x,int y){
	if(!x || !y) return x + y; int i = x;
	lc[i] = mrg(lc[x],lc[y]);
	rc[i] = mrg(rc[x],rc[y]);
	(lc[i] || rc[i]) ? psu(i,lc[i],rc[i]) : psu(i,y,x);
	return i;
}

ll cnt(int i){ return sum[rt[i]] * (i - 1) + val[rt[i]]; };

void upd(int x,int y){
	fa[y = fnd(y)] = x = fnd(x);
	res -= cnt(x) + cnt(y);
	rt[x] = mrg(rt[x],rt[y]);
	res += cnt(x);
}

signed main(){
	scanf("%d",&n);
	iota(begin(fa),end(fa),0);
	for(int i = 1;i <= n;++i){
		scanf("%d%d",a + i,b + i);
		c[i] = fnd(a[i]);
		fa[c[i]] = c[i] + 1;
		ins(b[i],rt[c[i]]);
	}
	iota(begin(fa),end(fa),0);
	ll sum = 0;
	for(int i = 1;i <= n;++i){
		res += cnt(c[i]);
		if(vis[c[i] + 1]) upd(c[i],c[i] + 1);
		if(vis[c[i] - 1]) upd(c[i] - 1,c[i]);
		sum += 1LL * a[i] * b[i];
		vis[c[i]] = true;
		printf("%lld\n",res - sum);
	}
	return 0;
}