专栏文章

方糖

TTTpandaS
P9528题解参与者 4已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miqc1w6j
此快照首次捕获于
2025/12/04 02:20
3 个月前
此快照最后确认于
2025/12/04 02:20
3 个月前
查看原文
方糖并不想被吃掉，所以（迟到地）给大家送来方糖社的新春祝福：
求最大匹配，利用扩展霍尔定理：一个任意二分图 (V1,V2,E)(V1,V2,E)，最大匹配为 ∣V1∣−max⁡S∈V1(∣S∣−∣N(S)∣)|V1|-\max_{S \in V1}(|S|-|N(S)|)。∣V1∣|V1| 即为 ∑[Ti=1]Ai\sum [T_i=1]A_i，SS 即为一些区间的蚂蚁的并，设为 ∪[li,ri]\cup [l_i,r_i]，那么 N(S)N(S) 即为这些区间向两边扩展 LL 的区间的并，设为 ∪[li−L,ri+L]\cup [l_i-L,r_i+L]。两个相邻区间间隔大于 2L2L，否则将两个区间合并为一个区间更优。
∣S∣|S| 和 ∣N(S)∣|N(S)| 对应蚂蚁和方糖的数量，设 aia_i 表示位置 ii 的蚂蚁数量，sis_i 为位置 ii 的方糖数量，答案即为
∑∑j=liriaj−∑j=li−Lri+Lsj=∑∑j=liri(aj−∑k=j−Lj+Lsk)+∑j=liri−1∑k=j−L+1j+Lsk\sum \sum_{j=l_i}^{r_i}a_j-\sum_{j=l_i-L}^{r_i+L}s_j=\sum \sum_{j=l_i}^{r_i}(a_j-\sum_{k=j-L}^{j+L}s_k)+\sum_{j=l_i}^{r_i-1}\sum_{k=j-L+1}^{j+L}s_k
令 j∈[li,ri]j \in [l_i,r_i] 表示 jj 被选择，设 dpl,r,0/1,0/1dp_{l,r,0/1,0/1} 表示区间 [l,r][l,r] 左端点和右端点是否被选择时的最大值。可以用线段树进行维护，同时为了合并左右儿子，对于每个区间 (l,r,mid)(l,r,mid) 还需要维护
∑k=mid−L+1mid+Lsk\sum_{k=mid-L+1}^{mid+L}s_k
的值。修改时注意 dpl,r,0,0≥0dp_{l,r,0,0} \geq 0。
加入蚂蚁时，对 XiX_i 位置单点加即可。
加入方糖时，会影响 [Xi−L,Xi+L][X_i-L,X_i+L] 这个区间的 dp 值。具体地，如果区间 (l,r,mid)⊆[Xi−L,Xi+L](l,r,mid) \subseteq [X_i-L,X_i+L]，那么 dp 值均会减少，而
∑k=mid−L+1mid+Lsk\sum_{k=mid-L+1}^{mid+L}s_k
的值会增加。此外，如果 Xi−L≤mid<Xi+LX_i-L\leq mid < X_i+L，那么该区间的
∑k=mid−L+1mid+Lsk\sum_{k=mid-L+1}^{mid+L}s_k
值也会增加。
实现需要离散化。
CPP
#include<bits/stdc++.h>
#define int long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N=5e5+5,inf=0x0d0007210d000721;
struct tree{
	int l,r,val,tag;
	int dp[2][2];
}t[N*4];
void pushup(int p){
	for(int x=0;x<=1;x++){
		for(int y=0;y<=1;y++){
			t[p].dp[x][y]=-inf;
		}
	}
	for(int x1=0;x1<=1;x1++){
		for(int y1=0;y1<=1;y1++){
			for(int x2=0;x2<=1;x2++){
				for(int y2=0;y2<=1;y2++){
					t[p].dp[x1][y2]=max(t[p].dp[x1][y2],t[lc].dp[x1][y1]+t[rc].dp[x2][y2]+(y1&x2)*t[p].val);
				}
			}
		}
	}
}
void add(int p,int val){
	t[p].val+=val;
	t[p].tag+=val;
	for(int x=0;x<=1;x++){
		for(int y=0;y<=1;y++){
			t[p].dp[x][y]-=val;
		}
	}
	t[p].dp[0][0]=max(t[p].dp[0][0],0ll);
}
void pushdown(int p){
	if(t[p].tag){
		add(lc,t[p].tag);
		add(rc,t[p].tag);
		t[p].tag=0;
	}
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r){
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
}
void addg(int p,int x,int y){
	if(t[p].l==t[p].r){
		t[p].dp[1][1]+=y;
		return;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(x<=mid){
		addg(lc,x,y);
	}
	else{
		addg(rc,x,y);
	}
	pushup(p);
}
void addf(int p,int l,int r,int x){
	if(l>r){
		return;
	}
	if(l<=t[p].l&&t[p].r<=r){
		add(p,x);
		return;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid){
		addf(lc,l,r,x);
	}
	if(mid+1<=r){
		addf(rc,l,r,x);
	}
	if(l<=mid&&mid+1<=r){
		t[p].val+=x;
	}
	pushup(p);
}
int Q,L;
int lsh[N],lshcnt;
struct opt{
	int t,x,a;
}o[N];
int ans;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>Q>>L;
	lshcnt=1;
	for(int i=1;i<=Q;i++){
		cin>>o[i].t>>o[i].x>>o[i].a;
		if(o[i].t==1){
			lsh[++lshcnt]=o[i].x;
		}
	}
	sort(lsh+1,lsh+lshcnt+1);
	lshcnt=unique(lsh+1,lsh+lshcnt+1)-lsh-1;
	build(1,1,lshcnt);
	for(int i=1;i<=Q;i++){
		if(o[i].t==1){
			ans+=o[i].a;
			int pos=lower_bound(lsh+1,lsh+lshcnt+1,o[i].x)-lsh;
			addg(1,pos,o[i].a);
		}
		else{
			int posl=lower_bound(lsh+1,lsh+lshcnt+1,o[i].x-L)-lsh,posr=upper_bound(lsh+1,lsh+lshcnt+1,o[i].x+L)-lsh-1;
			addf(1,posl,posr,o[i].a);
		}
		cout<<ans-max(max(t[1].dp[0][0],t[1].dp[0][1]),max(t[1].dp[1][0],t[1].dp[1][1]))<<'\n';
	}
	return 0;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...