贪心、前缀和

没想出来，看了提示悟了。

我仍然缺乏寻找确定步骤的意识，在这道题的转化过程中，从集合中移除的元素接下来会被放到哪个集合是不确定的，而没有被移除过的元素所在的集合是确定的。

考虑基于这个信息维护答案：计算没有被移除的元素的最大数量。

枚举一个后缀 $suf$ 并保留集合三中被 $[suf,n]$ 包含的元素，接下来需要求的是一个前缀的答案。

考虑前缀答案，使用前缀和 $s_r - s_{l-1}$ 表示 $[l,r]$ 中位于集合一的元素数量，使用前缀和 $w_r - w_{l-1}$ 表示 $[l,r]$ 中位于集合二的元素数量。

拆分前缀 $[1,pre]$ 的答案。

$$\max\limits_{i=0}^{pre} (s_i + w_{pre} - w_i) = w_{pre} + \max\limits_{i=0}^{pre} (s_i - w_i)$$

维护最大的 $s_i - w_i$ 的值。时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
int ks,kw,ksuf,d[200'005],s[200'005],w[200'005],suf[200'005];
void read(int n,int *sum){
    for(int i=1;i<=n;i++){
        static int x;
        scanf("%d",&x);
        sum[x]=1;
    }
}
int main(){
    scanf("%d%d%d",&ks,&kw,&ksuf);
    int n=ks+kw+ksuf;
    for(int i=1;i<=n;i++) s[i]=0,w[i]=0,suf[i]=0;
    read(ks,s),read(kw,w),read(ksuf,suf);
    for(int i=1;i<=n;i++) s[i]+=s[i-1],w[i]+=w[i-1];
    suf[n+1]=0;
    for(int i=n;i>=1;i--) suf[i]+=suf[i+1];
    for(int i=1;i<=n;i++) d[i]=max(s[i]-w[i],d[i-1]);
    int ans=0;
    for(int i=0;i<=n;i++) ans=max(ans,w[i]+d[i]+suf[i+1]);
    ans=n-ans;
    printf("%d\n",ans);
    return 0;
}