CF1257E（动态规划+思维+树状数组）

/*
 * 题意：有三个序列，每次操作可以把一个序列中的一个数移动到另一个序列中
 * 问：最少几次操作后，可以使得a序列里的所有数小于b里面的所有数，b里面的小于c里面的
 * 数字不重复
 * 做法：
 * 分别对三个序列排序，然后合并。
 * 求最大上升子序列，然后上升子序列里的数不动，只移动非序列里的，答案就是N-len
 * 求LIS时，用树状数组优化，时间复杂度O(nlogn）
 */
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+123;
const int inf=1e9;
int dp[maxn];
int c[maxn];
int N;
int lowbit (int x) {
    return x&-x;
}
void update (int x,int val) {
    for (int i=x;i<=N;i+=lowbit(i)) c[i]=max(c[i],val);
}
int getsum (int x) {
    int ans=0;
    for (int i=x;i;i-=lowbit(i)) ans=max(ans,c[i]);
    return ans;
}
int a[maxn];
int b[maxn];
int main () {
    int k1,k2,k3;
    scanf("%d%d%d",&k1,&k2,&k3);
    N=k1+k2+k3;
    int tot=0;
    for (int i=1;i<=k1;i++) scanf("%d",&b[i]);
    sort(b+1,b+k1+1);
    for (int i=1;i<=k1;i++) a[++tot]=b[i];

    for (int i=1;i<=k2;i++) scanf("%d",&b[i]);
    sort(b+1,b+k2+1);
    for (int i=1;i<=k2;i++) a[++tot]=b[i];

    for (int i=1;i<=k3;i++) scanf("%d",&b[i]);
    sort(b+1,b+k3+1);
    for (int i=1;i<=k3;i++) a[++tot]=b[i];

    int ans=0;
    for (int i=1;i<=N;i++) {
        dp[a[i]]=getsum(a[i])+1;
        ans=max(ans,dp[a[i]]);
        update(a[i],dp[a[i]]);
    }
    printf("%d
",N-ans);
}