CF1051G Distinctification题解

link

首先可以发现，题目给定的两种操作为我们提供了“反悔机制”，所以有：

结论 \(1\)：即任何一个可以到达的局面都能到达最优解。

利用这个结论，首先我们先去重。

继续提炼性质，与相差不到 \(1\) 的数为基准 \(+1\) 与 \(-1\) 操作，将这个数的变化范围限制在了一个区间，并且这个区间的数能够互换位置。所以我们按区间来考虑，利用上面的结论，可以将一个区间的数先全部放到最左边，在当前局面下，显然让 \(B_i\) 小的往右移动更优，那么得到：

结论 \(2\)：对于一个区间，使 \(b\) 递减最优。

同时容易得到：

结论 \(3\)：最终答案为 $ {\textstyle \sum_{}^{}(A_i'-A_i)\cdot B_i} ={\textstyle \sum_{}^{}A_i'\cdot B_i-A_i\cdot B_i}$

后者直接算，于是我们只需要维护一个区间的前者，并且能区间合并就行了，可以用线段树合并与并查集维护。

再说一下线段树怎么维护答案。，以 \(b\) 作为线段树的下标，考虑一个区间的答案怎样得到：
因为左区间的 \(B\) 小于右区间，需要交换左右区间，交换了之后的右区间的答案就是它这个子区间的答案，而左区间由于向右移动了，除了原本子区间的答案，还需要加上右区间的数对个数乘上左区间的 \(B\) 之和。

code：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define rpe(i,x) for(int i=_he[x];i;i=_ne[i])
#define mp(a,b) make_pair(a,b)
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef long double LD;
const int N=4e5+10;
const double pi=acos(-1);

int n,a[N],b[N],c[N];
int _fa[N];
void _init(){rep(i,1,N-2)_fa[i]=i;}
int get(int x){return _fa[x]==x?x:_fa[x]=get(_fa[x]);}

int ls[25*N],rs[25*N],rt[N],node;

struct stree{
	LL sum,val;
	int sz;
}t[25*N];
void pushup(int p)
{
	t[p].sz=t[ls[p]].sz+t[rs[p]].sz;
	t[p].sum=t[ls[p]].sum+t[rs[p]].sum;
	t[p].val=t[ls[p]].val+t[rs[p]].val+t[ls[p]].sum*t[rs[p]].sz;
}
void change(int &p,int l,int r,int x)
{
	if(!p)p=++node;
	if(l==r)t[p].sum=t[p].val=x,t[p].sz=1;
	else
	{
		int mid=l+r>>1;
		x<=mid?change(ls[p],l,mid,x):change(rs[p],mid+1,r,x);
		pushup(p);
	}
}
int merge(int x,int y,int l,int r)
{
	if(!x||!y)return x|y;
	int mid=l+r>>1;
	ls[x]=merge(ls[x],ls[y],l,mid),rs[x]=merge(rs[x],rs[y],mid+1,r);
		
	if(!ls[x]&&!rs[x])t[x].sz+=t[y].sz,t[x].sum+=t[y].sum,t[x].val+=t[y].val;
	else pushup(x);
	return x;
}
LL calc(int x){return t[rt[x]].val+t[rt[x]].sum*(x-1);}
LL ans;
void mer(int x,int y)
{
	_fa[y=get(y)]=(x=get(x));
	ans-=calc(x)+calc(y);
	rt[x]=merge(rt[x],rt[y],1,n);
	ans+=calc(x);
}

bool fl[N];
int main()
{
	scanf("%d",&n);
	_init();
	rep(i,1,n)
	{
		scanf("%d%d",&a[i],&b[i]);
		c[i]=get(a[i]);
		_fa[c[i]]=c[i]+1;
		change(rt[c[i]],1,n,b[i]);
	}
	_init();
	rep(i,1,n)
	{
		ans+=calc(c[i]);
		if(fl[c[i]-1])mer(c[i]-1,c[i]);
		if(fl[c[i]+1])mer(c[i],c[i]+1);
		fl[c[i]]=1;
		ans-=1ll*a[i]*b[i];
		printf("%lld\n",ans);
	}	
	return 0;
}