题解：P10685 [COTS/CETS 2024] 兔子 Zečevi

· · 题解

分析

首先二分答案 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;
}