P13509 [OOI 2024] Almost Certainly 题解

考虑维护一棵值域线段树

T

。对于每一个

i

，将

T

上

[b_i+1,a_i]

的位置的值加

1

，于是

a

可以变成

b

当且仅当

T

上每一个位置都大于等于

0

，此时需要的操作次数为

\sum\limits_{i=1}^m a_i-\sum\limits_{i=1}^m b_i

。

由于「几乎等价」等价于「各删除一个数后完全相等」，设我们删除的是

a_x

和

b_y

，那么我们希望删除的

b_x-a_y

尽可能大，这样才能使操作次数尽可能小。但是我们要保证删除后

T

上每一个位置都大于等于

0

，所以需要满足

T

上

[a_y,b_x]

的每一个位置都大于等于

1

，于是在

T

上计算最长的大于等于

1

的区间的长度即可。

可以离散化一下，时间复杂度

\mathcal O(n \log n)

。

#define int long long
const int N=2e5+5,inf=2e9;
int n,m,ans,a[N],b[N],t[N<<1],val[N<<3],lef[N<<3],rig[N<<3],mid[N<<3],sum[N<<3];
bool tag[N<<3];
void upd(int g){
	sum[g]=sum[g<<1]+sum[g<<1|1];
	lef[g]=max(lef[g<<1],val[g<<1]+lef[g<<1|1]);
	lef[g]=max(lef[g],val[g<<1]);
	rig[g]=max(rig[g<<1|1],rig[g<<1]+val[g<<1|1]);
	rig[g]=max(rig[g],val[g<<1|1]);
	mid[g]=max(mid[g<<1],mid[g<<1|1]);
	mid[g]=max(mid[g],rig[g<<1]+lef[g<<1|1]);
	mid[g]=max(mid[g],max(lef[g<<1|1],rig[g<<1]));
	val[g]=val[g<<1]+val[g<<1|1];
}
void down(int g){
	if(tag[g]){
		tag[g<<1]=tag[g<<1|1]=1;
		tag[g]=0;
		mid[g<<1]=lef[g<<1]=rig[g<<1]=val[g<<1]=sum[g<<1];
		mid[g<<1|1]=lef[g<<1|1]=rig[g<<1|1]=val[g<<1|1]=sum[g<<1|1];
	}
}
void build(int g,int l,int r){
	tag[g]=0;
	if(l==r){
		sum[g]=t[r]-t[r-1];
		mid[g]=0;
		lef[g]=rig[g]=val[g]=-inf;
		return;
	}
	int m=(l+r)>>1;
	build(g<<1,l,m);
	build(g<<1|1,m+1,r);
	upd(g);
}
void modify(int g,int l,int r,int x,int y){
	if(x<=l&&r<=y) return mid[g]=lef[g]=rig[g]=val[g]=sum[g],tag[g]=1,void();
	if(r<x||y<l) return;
	int m=(l+r)>>1;
	down(g);
	modify(g<<1,l,m,x,y);
	modify(g<<1|1,m+1,r,x,y);
	upd(g);
}
void solve(){
	cin>>n,ans=0;
	for(int i=1;i<=n;i++) cin>>a[i],t[i]=a[i];
	for(int i=1;i<=n;i++) cin>>b[i],t[i+n]=b[i];
	sort(t+1,t+n+n+1);
	m=unique(t+1,t+n+n+1)-t-1;
	build(1,1,m);
	for(int i=1;i<=n;i++){
		ans+=a[i]-b[i];
		int x=lb(t+1,t+m+1,b[i])-t,y=lb(t+1,t+m+1,a[i])-t;
		modify(1,1,m,x+1,y);
		cout<<ans-max(mid[1],max(lef[1],max(rig[1],val[1])))<<' ';
	}
	cout<<endl;
}

P13509 [OOI 2024] Almost Certainly 题解

文章操作

相关推荐

评论

P13509 [OOI 2024] Almost Certainly 题解