自动搬运

查看原文

来自洛谷，原作者为

	D_F_S 本来无一物,误入藕花深处。

搬运于2025-08-24 22:00:35，当前版本为作者最后更新于2022-03-14 22:56:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

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;
}