Educational Codeforces Round 76 (Rated for Div. 2) E. The Contest(线段树+模拟)

题目链接
大意：给你三个数组，你 可以把任意数组的任意 元素 放到 任意数组中，
使得第一个数组是前缀，第三个数组是后缀，剩下的元素在第二个数组。
我们把三个东西分别记为 $1,2,3$1,2,3，那么相当于 $1-n$1−n的元素是连续 的1和连续的2和连续的3组成 。

我们用暴力的思想，就是枚举两个分界点嘛。

然后用数据结构优化这个暴力，先假设只有2，3，那么我们枚举2，3的分界点，记录每个分界点的需要的操作数，记为数组 $t$t。
用 $t$t建线段树维护最小值。
然后就是遍历1，2的分界点，根据这个元素的值 对线段树进行 $update$update操作，维护全局最小值即可啦。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
#define fi first
#define se second
#define pb push_back
int len[4],a[N],n;
int f[N][2],b[N];
int T[N<<2];
#define mid (l+r>>1)
#define ls o<<1
#define rs o<<1|1
void build(int o,int l,int r){
    if(l==r){
        T[o]=b[l];
        return ;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    T[o]=min(T[ls],T[rs]);
}
int laz[N<<2];
void ud(int o,int l,int r,int x,int y){
    if(x<=l&&y>=r){
        T[o]--;
        laz[o]--;
        return ;
    }
    if(laz[o]!=0){
        laz[ls]+=laz[o];
        laz[rs]+=laz[o];
        T[ls]+=laz[o];
        T[rs]+=laz[o];
        laz[o]=0;
    }
    if(x<=mid)ud(ls,l,mid,x,y);
    if(y>mid)ud(rs,mid+1,r,x,y);
    T[o]=min(T[ls],T[rs]);
}
int main() {
    ios::sync_with_stdio(false);
    for(int i=1;i<=3;i++)cin>>len[i],n+=len[i];
    for(int i=1;i<=3;i++){
        for(int j=1;j<=len[i];j++){
            int x;
            cin>>x;
            a[x]=i;
        }
    }
    int ans=n-max({len[1],len[2],len[3]});
    int q=0,p=0;
    for(int i=1;i<=n;i++)q+=(a[i]!=3);
    for(int i=0;i<=n;i++){
        if(!i)b[i]=q;
        else{
            if(a[i]!=3)q--;
            if(a[i]!=2)p++;
            b[i]=p+q;
            ans=min(ans,b[i]);
        }
    }
    build(1,0,n);
    int tmp=0;
    for(int i=1;i<=n;i++){
        if(a[i]!=3)ud(1,0,n,0,i-1);
        if(a[i]!=2)ud(1,0,n,i,n);
        if(a[i]!=1)tmp++;
        ans=min(ans,tmp+T[1]);
    }
    cout<<ans<<'\n';
    return 0;
}