CF1051G - Distinctification

Posted on Edited on In

CF1051G - Distinctification

题目大意

对于一个二元组集合 \(\{(a_i,b_i)\}\)

每次可以进行操作

1.如果存在 \(a_i=a_j\) ，可以花费 \(b_i\) 代价 \(a_i\) 增加1

2.如果存在 \(a_i=a_{j}+1\) ，可以花费 \(-b_i\) 代价使 \(a_i\) 减少1

现在依次向集合插入 \(n\) 个二元组，求在所有时刻，对于当前的集合进行操作

最终使得不存在 \(a_i=a_j\) 时的最小花费（可以为负）


分析

容易发现对于给定的 \(a_i\) 集合，最终 \(a_i\) 的集合唯一固定

具体的，每次插入一个数值 \(x\) ，如果出现重复就会不停将 \(x\) 向后推推推

而事实上答案为 \(\sum b_i\cdot (a'_i-a_i)\) ，那么只需要最小化 \(\sum b_ia'_i\)

容易发现在任意时刻，如果 \([L,R]\) 内所有 \(a_i\) 都出现，就可以任意交换他们的 \(b_i\)

那么最终状态中每一个 \(a_i\) 连通块内，按照 \(b_i\) 从大到小排序即可

每次插入一个元素维护连通块之间的合并以及求出 \(\sum b_ia'_i\) 即可

可以用启发式合并/线段树合并维护

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
const int N=4e5+10,M=N*19,INF=1e9+10;

int n;
int ls[M],rs[M],c[M],cnt;
ll s[M],ans[M];
ll Ans;

int F[N],rt[N];
int Find(int x){ return F[x]==x?x:F[x]=Find(F[x]); }
void Up(int x){
	c[x]=c[ls[x]]+c[rs[x]],s[x]=s[ls[x]]+s[rs[x]];
	ans[x]=ans[ls[x]]+ans[rs[x]]+c[rs[x]]*s[ls[x]];
}
void Upd(int &p,int l,int r,int x){
	if(!p) p=++cnt;
	if(l==r) { c[p]=1,s[p]=x; return; }
	int mid=(l+r)>>1;
	x<=mid?Upd(ls[p],l,mid,x):Upd(rs[p],mid+1,r,x);
	Up(p);
}
int Union(int x,int y,int l=1,int r=n){
	if(!x||!y) return x|y;
	int mid=(l+r)>>1;
	ls[x]=Union(ls[x],ls[y],l,mid),rs[x]=Union(rs[x],rs[y],mid+1,r);
	return Up(x),x;
}

void Add(int x,int k){
	x=Find(x);
	Ans+=k*(x*s[rt[x]]+ans[rt[x]]);
}

int main(){
	n=rd();
	rep(i,1,n){
		int x=rd(),y=rd();
		Ans-=1ll*x*y;
		int f=Find(x);
		if(!f) f=F[x]=x;
		else Add(f,-1),F[f+c[rt[f]]]=f;
		Upd(rt[f],1,n,y);
		while(x=Find(x),y=Find(x-1)) {
			Add(y,-1);
			F[x]=x-1;
			rt[y]=Union(rt[y],rt[x]);
		}
		while(x=Find(x),y=Find(x+c[rt[x]])) {
			Add(y,-1);
			F[x+c[rt[x]]]=x;
			rt[x]=Union(rt[x],rt[y]);
		}
		Add(x,1),printf("%lld\n",Ans);
	}
}