专栏文章

2025_4_28 T3

EEvan_Leo_Azir
题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mipgtlki
此快照首次捕获于
2025/12/03 11:46
3 个月前
此快照最后确认于
2025/12/03 11:46
3 个月前
查看原文
属于合格的NOIP T3 ,有下位紫难度 CF 2500左右吧（但也不至于多棘手）
题目中两集合为 AA , BB
首先观察等式
ans=min⁡x∈A,y∈Bmax⁡(ax+ay,bx+by)ans=\min_{x \in A,y\in B} \max(a_x+a_y,b_x+b_y)
注意到，max⁡\max函数中的两项分别由AA与BB的集合元素构成，如果要直接维护max⁡\max函数的值，状态数显然十分大——为两集合元素数之积，故考虑把式子拆开
思考一下，当max⁡\max函数中，我们取出的值为ax+aya_x+a_y时，需要满足什么条件？
条件如下
ax+ay≥bx+bya_x+a_y\ge b_x+b_y
同理，当取出了bx+byb_x+b_y时
ax+ay≤bx+bya_x+a_y\le b_x+b_y
考虑移项，使等式一边的值来自同一集合，即
ax−bx≥by−ayax−bx≤by−aya_x-b_x\ge b_y-a_y \\ a_x-b_x\le b_y-a_y
此时，为了方便表示，我们设
hx=ax−bx(x∈A)hx=bx−ax(x∈B)h_x=a_x-b_x (x\in A) \\ h_x=b_x-a_x (x\in B)
最终发现，我们可以用hxh_x比大小，来确定max⁡\max最终可以取哪一项
因为题目有多组询问，所以我们要设法维护ansans，此时有两种思路，第一是通过上一个ansans递推目前的ansans，第二种即为采用某些数据结构，直接回答
前者在只有加数自然方便，但遇到删除操作时便束手无策了，故我们采用后者的思路——使用数据结构
很直觉的，我们对于hxh_x开一颗权值线段数，离线下所有操作后，将hxh_x离散化，以其作为下标
那对于线段树的每个节点，我们要存什么？
线段树最重要的是合并，即具有结合律——hyh
我们维护当前节点本身可以找出的答案，假设左右儿子为lsls,rsrs，目前pushuppushup的节点为rtrt,显然有
ansrt=min⁡(ansls,ansrs)ans_{rt}=\min(ans_{ls},ans_{rs})
同样，为了合并，我们还要维护当前节点内最小的ax,bx(x∈A)a_x,b_x(x\in A),ay,by(y∈B)a_y,b_y(y\in B)
所以，这启发我们，对于底层的节点（即 treel=treertree_l=tree_r)维护一个set
因为是以hxh_x作下标的权值线段树，故rsrs的hxh_x大于lsls的hxh_x，所以
ans=min⁡(ans,min⁡(rsax+lsay,rsby+lsbx))(x∈A,y∈B)ans=\min(ans,\min(rs_{a_x}+ls_{a_y},rs_{b_y}+ls_{b_x}))(x\in A,y\in B)
此时，对于加入或删点，先O(log⁡q)O(\log q)操作底层的set，再一步步传上来即可
时间复杂度O(qlog⁡q)O(q\log q)
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+10,inf=1e17+10;
int q,len;
int lisan[maxn];
struct QUE{
	int opt,d,a,b,id,deta;
}que[maxn];
struct SEGMENT_TREE{//0,1指A集合 2,3指B集合,0 2指a,1 3指b 
	int minans; 
	int mi[4];
}tree[maxn<<2];
multiset<int>s[maxn][4];
int read()
{
	int ret=0,w=1;char ch=0;
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
	return ret*w;
}
void pushup(int ret)
{
	for(int i=0;i<4;i++) tree[ret].mi[i]=min(tree[ret<<1].mi[i],tree[ret<<1|1].mi[i]);
	tree[ret].minans=min(tree[ret<<1].minans,tree[ret<<1|1].minans);
	tree[ret].minans=min(tree[ret].minans,min(tree[ret<<1].mi[2]+tree[ret<<1|1].mi[0],
	tree[ret<<1].mi[1]+tree[ret<<1|1].mi[3]));
}
void build(int ret,int l,int r)
{
	tree[ret].minans=inf;
	for(int i=0;i<4;i++) tree[ret].mi[i]=inf;
	if(l==r) {for(int i=0;i<4;i++) s[l][i].insert(inf);}
	else
	{
		int mid=(l+r)>>1;
		build(ret<<1,l,mid);build(ret<<1|1,mid+1,r);
	}
}
void change(int ret,int l,int r,int id)
{
	if(l==r)
	{
		int x=que[id].d?2:0;
		if(que[id].opt)
		{
			s[l][x].insert(que[id].a);
			s[l][x+1].insert(que[id].b);
		}else
		{
			s[l][x].erase(s[l][x].find(que[id].a));
			s[l][x+1].erase(s[l][x+1].find(que[id].b));
		}
		for(int i=0;i<4;i++) tree[ret].mi[i]=*s[l][i].begin();
		tree[ret].minans=min(tree[ret].mi[0]+tree[ret].mi[2],tree[ret].mi[1]+tree[ret].mi[3]);
	}else
	{
		int mid=(l+r)>>1;
		if(que[id].id<=mid) change(ret<<1,l,mid,id);
		else change(ret<<1|1,mid+1,r,id);
		pushup(ret);
	}
}
void inpu()
{
	q=read();
	for(int i=1;i<=q;i++)
	{
		que[i].opt=read(),que[i].d=read(),que[i].a=read(),que[i].b=read();
		que[i].deta=lisan[i]=que[i].d?que[i].b-que[i].a:que[i].a-que[i].b;
	}//操作离线
}
void pre()
{
	sort(lisan+1,lisan+q+1);
	len=unique(lisan+1,lisan+q+1)-lisan-1;
	build(1,1,q);
}//离散化与建树
void deal()
{
	for(int i=1;i<=q;i++)
	{
		que[i].id=lower_bound(lisan+1,lisan+len+1,que[i].deta)-lisan;
		change(1,1,q,i);
		printf("%lld\n",tree[1].minans>(int)4e9?-1:tree[1].minans);
	}
}
void solve()
{
	inpu();
	pre();
	deal();
}
signed main()
{
	int t=1;
	while(t--) solve();
	return 0;
}

评论

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

正在加载评论...