CF1257E The Contest

做一遍前缀和，令 \(b_{x,y}\) 表示序列 \(x\) 包含 \(1\sim y\) 的数字有几个。考虑枚举第一个序列保留哪个前缀 \(1\sim i\)，对于第三个序列，如果保留了后缀 \(j\sim n(i<j)\)。

考虑哪些数需要被移掉，这样恰好能不重不漏。那么答案就是：

可以发现只要维护 \(-b_{2,j-1}+b_{3,j-1}\) 的后缀 \(\min\) 就好了，剩下的都是定值。时间复杂度 \(O(n)\)，头尾稍微注意一下。

code:

#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define Min(x,y)((x)<(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
#define Down(i,x,y)for(i=x;i>=(y);i--)
int a1[N],a2[N],a3[N],suf[N];
int read()
{
	int A;
	bool K;
	char C;
	C=A=K=0;
	while(C<'0'||C>'9')K|=C=='-',C=getchar();
	while(C>'/'&&C<':')A=(A<<3)+(A<<1)+(C^48),C=getchar();
	return(K?-A:A);
}
int main()
{
	int k1,k2,k3,n,i,ans=INT_MAX;
	k1=read(),k2=read(),k3=read();
	n=k1+k2+k3;
	For(i,1,k1)a1[read()]=1;
	For(i,1,k2)a2[read()]=1;
	For(i,1,k3)a3[read()]=1;
	For(i,2,n)
	{
		a1[i]+=a1[i-1];
		a2[i]+=a2[i-1];
		a3[i]+=a3[i-1];
	}
	suf[n]=-a2[n]+a3[n];
	Down(i,n-1,0)suf[i]=Min(suf[i+1],-a2[i]+a3[i]);
	For(i,0,n)ans=Min(ans,suf[i]+a1[n]-a1[i]+a2[n]+a2[i]);
	cout<<ans;
	return 0;
}