P4477 [BJWC2018]基础匹配算法练习题 题解

· · 题解 

一篇使用 莫队+单点修改线段树 解决的题解

Solution：

因为是多次区间询问，考虑使用莫队。

又因为是匹配，只与权值有关，不妨先将 A 排序。

对于 B_i，它所能匹配到的数构成 A 的一个前缀。只要这个前缀中还有一个数未匹配，就可将它与 B_i 匹配。

这样就有了一个莫队增删时用线段树维护最大匹配数量的思路：

线段树以 1\sim N 为下标，区间内维护三个信息：size、sum、ans 分别表示 区间大小、区间内数的数量，区间内最大匹配数量。

当 C 中新增一个数 B_i 时，用二分找出它能匹配到的最大 A_i 的位置，如果当前位置还未被匹配（即 ans=0），则当前位置 sum 与 ans 都 +1，否则只有 sum+1。删数时的操作类似，当 sum 减至 0 时 ans-1。

关于区间合并，sum 直接相加即可，而对于 ans，首先也将左右区间的 ans 相加，然需考虑右区间的 B 与左区间的 A 匹配，贡献为 min(\text{左区间剩余 }A \text{ 的个数},\text{右区间多余 }B \text{ 的个数})。

对于每个 B_i，我们都能保证它与所对应的 A 的前缀中的每个数尝试了匹配，且会优先与最靠近限度的数匹配，因此能保证匹配数最大。

至此，便可统计出最大匹配数，时间复杂度为 O(M\sqrt{M}\log n)。

Code:

#include<bits/stdc++.h>
#define inl inline
#define L (p<<1)
#define R (L|1)
#define mid ((l+r)>>1)
using namespace std;
const int N=152505,M=52505;
struct node {int l,r,id; }as[M];
struct node1 {int si,su,an; }tr[N*4];   // 区间大小，区间内所有数的数量，区间内匹配上的数的数量 
int n,m,sqm,Z,Q,ans[M],a[N],b[M],bl[M];
inl bool operator <(node a,node b)
{
    if(bl[a.l]!=bl[b.l]) return a.l<b.l;
    return (bl[a.l]&1)?a.r>b.r:a.r<b.r;     // 奇偶优化 
}
inl int Read()
{
    int s=0; char c;
    while(!isdigit(c=getchar()));
    for(;isdigit(c);c=getchar()) s=s*10+c-'0'; return s;
}
inl void Write(int x)
{
    int cnt=0,s[10]; do s[++cnt]=x%10; while(x/=10);
    while(cnt--) putchar(s[cnt+1]+'0');
}
inl void Pushup(int p)
{
    tr[p].su=tr[L].su+tr[R].su;
    tr[p].an=tr[L].an+tr[R].an;
    tr[p].an+=min(max(tr[L].si-tr[L].an,0),tr[R].su-tr[R].an);
        // max(tr[L].si-tr[L].an,0) 为左区间剩余个数，tr[R].su-tr[R].an 为右区间多余个数 
}
inl void Build(int p,int l,int r)
{
    tr[p].si=r-l+1; if(l==r) return;
    Build(L,l,mid); Build(R,mid+1,r);
}
inl void Modify(int p,int l,int r,int va,int fl)
{
    if(l==r)
    {
        if(Z-va<a[l]) return;   // 无法匹配，此时 l=r=1
        if(tr[p].su==0) tr[p].an=1;
        tr[p].su+=fl;
        if(tr[p].su==0) tr[p].an=0;
        return;
    }
    Z-va<a[mid+1]?Modify(L,l,mid,va,fl):Modify(R,mid+1,r,va,fl);
    Pushup(p);
}
int main()
{
    n=Read(); m=Read(); Z=Read(); sqm=sqrt(m);
    for(int i=1;i<=n;++i) a[i]=Read();
    for(int i=1;i<=m;++i) b[i]=Read(), bl[i]=i/sqm;
    sort(a+1,a+n+1); Build(1,1,n);

    Q=Read();
    for(int i=1;i<=Q;++i) as[i]=(node){Read(),Read(),i};
    sort(as+1,as+Q+1);
    for(int i=1,l=1,r=0;i<=Q;++i)
    {
        while(l>as[i].l) Modify(1,1,n,b[--l],1);
        while(r<as[i].r) Modify(1,1,n,b[++r],1);
        while(l<as[i].l) Modify(1,1,n,b[l++],-1);
        while(r>as[i].r) Modify(1,1,n,b[r--],-1);
        ans[as[i].id]=tr[1].an;
    }
    for(int i=1;i<=Q;++i) Write(ans[i]), putchar('\n');
    return 0;
}