自动搬运

查看原文

来自洛谷，原作者为

	oMin0 oahzgnim| 悲欢离合总无情，一任阶前点滴到天明

搬运于2025-08-24 23:00:15，当前版本为作者最后更新于2024-07-09 15:13:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析

首先二分答案 $ans$，我们以下解决判定问题。

不妨假设兔子每次只能吃 $1$ 千克的胡萝卜，那么就要求第 $i$ 次兔子需要进食 $\max(0,ans-p_i)$ 次，且其第 $j$ 次进食时的位置必须在 $[x_i,x_i+p_i+j-1]$ 区间内。

这是左部点向右部点区间连边的二分图匹配问题，最近校内模拟赛里也出现过。记左部点的连边区间是 $[l_i,r_i]$，有一个正确性相当自然的贪心策略是“从小到大枚举右部点 $x$，将其与 $l_i\geq x$ 且 $r_i$ 最小的左部点匹配”，因为如果两右部点 $i<j$ 的匹配点 $x,y$ 满足 $l_{y}\leq i\leq r_{y}\leq r_{x}$ 的话可以交换它们。

那么对数轴从左到右扫描线，则以上策略的实现是：当扫到 $x_i$ 时加入右端点分别为 $x_i+p_i,x_i+p_i+1,\dots,x_i+ans-1$ 的若干个区间，当扫到 $y_i$ 时把右端点 $\geq y_i$ 的前 $t_i$ 小区间匹配掉，最终答案合法当且仅当所有的区间都被匹配。用线段树快速维护这几种操作即可（区间加，把区间置成 $0$，查区间和）。

时间复杂度 $O(n\log^2 V)$，可以通过本题。

代码

/*
  author: honglan0301
  Sexy_goodier _ xiaoqing
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <queue>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <cmath>
#include <random>
#include <set>
#include <bitset>
#include <assert.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long

int n,m,flag,lim;
pair<int,int> x[100005],y[100005];

struct tree
{
	int ls,rs,tag,len,sum;
}tree[10000005];
int cntd,rt;

#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define l(x) tree[x].len
#define n(x) tree[x].sum
#define tg(x) tree[x].tag
#define md(x,y) ((x+y)>>1)
#define push_up(x) n(x)=n(ls(x))+n(rs(x))
#define cz(k,p) tg(p)+=k,n(p)+=1ll*k*l(p)

void push_down(int p)
{
	if(tg(p))
	{
		if(!ls(p)) ls(p)=++cntd,l(ls(p))=(l(p)+1)/2; cz(tg(p),ls(p));
		if(!rs(p)) rs(p)=++cntd,l(rs(p))=l(p)/2; cz(tg(p),rs(p)); tg(p)=0;
	}
}
void cza(int l,int r,int x,int y,int k,int &p)
{
	if(!p) p=++cntd,l(p)=r-l+1; if(l>=x&&r<=y) return cz(k,p),void(); int mid=md(l,r); push_down(p);
	if(mid>=x) cza(l,mid,x,y,k,ls(p)); if(mid<y) cza(mid+1,r,x,y,k,rs(p)); push_up(p);
}
void czf(int l,int r,int k,int p)
{
	if(l==r) return n(p)-=k,void(); int mid=md(l,r); push_down(p);
	if(n(ls(p))<=k) czf(mid+1,r,k-n(ls(p)),rs(p)),ls(p)=0; else czf(l,mid,k,ls(p)); push_up(p);
}
int askm(int l,int r,int p)
{
	if(l==r) return l; int mid=md(l,r); push_down(p);
	if(n(ls(p))) return askm(l,mid,ls(p)); else return askm(mid+1,r,rs(p));
}

int sums=0;
void ins(pair<int,int> xx,int k)
{
	if(xx.se>=k) return;
	sums+=(k-1)-xx.se+1;
	cza(0,lim,xx.fi+xx.se,xx.fi+k-1,1,rt);
}
void del(pair<int,int> xx,int k)
{
	flag&=askm(0,lim,rt)>=xx.fi;
	if(n(rt)<=xx.se) rt=0; else czf(0,lim,xx.se,rt);
}

void clr()
{
	for(int i=1;i<=cntd;i++) ls(i)=rs(i)=n(i)=tg(i)=l(i)=0; cntd=rt=0;
}
int ck(int k)
{
	int nzl=1,nzr=1; flag=1;
	while(nzl<=n&&nzr<=m)
	{
		if(x[nzl].fi<=y[nzr].fi) ins(x[nzl++],k);
		else del(y[nzr++],k);
	}
	while(nzl<=n) ins(x[nzl++],k);
	while(nzr<=m) del(y[nzr++],k);
	flag&=askm(0,lim,rt)==lim; clr(); return flag;
}

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>x[i].fi>>x[i].se;
	for(int i=1;i<=m;i++) cin>>y[i].fi>>y[i].se;
	sort(x+1,x+n+1); sort(y+1,y+m+1);
	int l=0,r=0;
	for(int i=1;i<=n;i++) r+=x[i].se;
	for(int i=1;i<=m;i++) r+=y[i].se; r/=n;
	lim=r+2000000000ll;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(ck(mid)) l=mid+1; else r=mid-1;
	}
	cout<<r<<endl;
}