题解 CF392D 【Three Arrays】

题解

首先肯定是要枚举一个的，我枚举的是（中的位置）。

但我们不能从小到大枚举，要从大到小枚举。

为什么呢？从大到小枚举的话，相当于是每次会多一些限制，这样比较好维护（如果是撤销限制，那不是很麻烦吗）。

考虑会多什么限制呢？

就是那个数原来是在中被消灭的，现在不能在中被消灭了，那么就得在或中被消灭。

那到底是在中还是中呢？

这就到了本题的关键地方了，我们把在中消灭的位置看成横坐标，在中消灭的位置看成纵坐标。这样的话，在二维平面中就有了一些点，我们要选一个横坐标和一个纵坐标，使得所有点要么横坐标，要么纵坐标。我们要求最小的。

怎么维护二维平面上的点呢，我们用线段树下标代替横坐标，用线段树维护纵坐标。

具体怎么维护，比如一个点，那么相当于横坐标的纵坐标都必须，相当于的位置上区间覆盖最大值。

由于是，所以我们相当于在线段树下标为的地方都应该加上。

这就让我们不能用普通办法区间覆盖了。因为有些位置上最大值是大于要覆盖的数的，但你不知道，你会以为那个位置小，就用那个位置+覆盖的数来修改答案。

这时候，你发现随着横坐标的增大，纵坐标是单调不增的。那么我们找到第一个覆盖的值的位置（是当前要覆盖的值），然后就可以区间覆盖了，因为这时横坐标上覆盖的值都了，那么你用最小的位置+覆盖的数来修改答案就是对的。

如何找到第一个覆盖的值的位置呢？

线段树上二分即可。

细节：

可能有些是只在或中出现，那么相当于都有一个下界，没关系（线段树区间查询），的话我们就区间覆盖啊，做法同上。

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define last Last
const int N=1e6+5;
int n,RR,gs,ans=1e9,Xma,Yma,ma[N],a[N],b[N],c[N],d[N],La[N],Lb[N],Lc[N],lst[N],tree[N*4],mi[N*4],lazy[N*4];
char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
void build(int nod,int l,int r)
{
    if(l==r)
    {
        tree[nod]=mi[nod]=l;
        return;
    }
    int mid=(l+r)/2;
    build(nod*2,l,mid);
    build(nod*2+1,mid+1,r);
    tree[nod]=min(tree[nod*2],tree[nod*2+1]);
    mi[nod]=min(mi[nod*2],mi[nod*2+1]);
}
void pushdown(int nod)
{
    if(!lazy[nod])return;
    mi[nod*2]=max(mi[nod*2],tree[nod*2]+lazy[nod]);
    mi[nod*2+1]=max(mi[nod*2+1],tree[nod*2+1]+lazy[nod]);
    lazy[nod*2]=max(lazy[nod*2],lazy[nod]);
    lazy[nod*2+1]=max(lazy[nod*2+1],lazy[nod]);
    ma[nod*2]=max(ma[nod*2],lazy[nod]);
    ma[nod*2+1]=max(ma[nod*2+1],lazy[nod]);
    lazy[nod]=0;
}
void change(int nod,int l,int r,int L,int R,int val)
{
    if(l==L&&r==R)
    {
        ma[nod]=max(ma[nod],val);
        mi[nod]=max(mi[nod],tree[nod]+val);
        lazy[nod]=max(lazy[nod],val);
        return;
    }
    pushdown(nod);
    int mid=(l+r)/2;
    if(R<=mid)change(nod*2,l,mid,L,R,val);
    else if(L>mid)change(nod*2+1,mid+1,r,L,R,val);
    else{
        change(nod*2,l,mid,L,mid,val);
        change(nod*2+1,mid+1,r,mid+1,R,val);
    }
    mi[nod]=min(mi[nod*2],mi[nod*2+1]);
    ma[nod]=min(ma[nod*2],ma[nod*2+1]);
}
int find(int nod,int l,int r,int L,int R)
{
    if(l==L&&r==R)return mi[nod];
    pushdown(nod);
    int mid=(l+r)/2;
    if(R<=mid)return find(nod*2,l,mid,L,R);
    else if(L>mid)return find(nod*2+1,mid+1,r,L,R);
    else return min(find(nod*2,l,mid,L,mid),find(nod*2+1,mid+1,r,mid+1,R));
}
int query(int nod,int l,int r,int val)
{
    if(l==r)
    {
        if(ma[nod]>=val)return l+1;
        else return l;
    }
    pushdown(nod);
    int mid=(l+r)/2;
    if(ma[nod*2]>=val)return query(nod*2+1,mid+1,r,val);
    else return query(nod*2,l,mid,val);
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        d[++gs]=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        b[i]=read();
        d[++gs]=b[i];
    }
    for(int i=1;i<=n;i++)
    {
        c[i]=read();
        d[++gs]=c[i];
    }
    sort(d+1,d+gs+1);
    gs=unique(d+1,d+gs+1)-d-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(d+1,d+gs+1,a[i])-d;
    for(int i=1;i<=n;i++)b[i]=lower_bound(d+1,d+gs+1,b[i])-d;
    for(int i=1;i<=n;i++)c[i]=lower_bound(d+1,d+gs+1,c[i])-d;
    for(int i=1;i<=gs;i++)lst[i]=0;
    for(int i=1;i<=n;i++)
    {
        if(lst[a[i]])continue;
        lst[a[i]]=1;
        La[a[i]]=i;
    }
    for(int i=1;i<=gs;i++)lst[i]=0;
    for(int i=1;i<=n;i++)
    {
        if(lst[b[i]])continue;
        lst[b[i]]=1;
        Lb[b[i]]=i;
    }
    for(int i=1;i<=gs;i++)lst[i]=0;
    for(int i=1;i<=n;i++)
    {
        if(lst[c[i]])continue;
        lst[c[i]]=1;
        Lc[c[i]]=i;
    }
    build(1,0,n);
    for(int i=1;i<=n;i++)
        if((!La[b[i]])&&(Lb[b[i]]==i))
        {
            if(!Lc[b[i]])Xma=max(Xma,i);
        }
    for(int i=1;i<=n;i++)
        if((!La[c[i]])&&(Lc[c[i]]==i))
        {
            if(!Lb[c[i]])Yma=max(Yma,i);
        }
    for(int i=1;i<=n;i++)
        if((!La[b[i]])&&(Lb[b[i]]==i))
        {
            if(Lc[b[i]])
            {
                int x=query(1,0,n,Lc[b[i]]);
                if(x<=i-1)change(1,0,n,x,i-1,Lc[b[i]]);
            }
        }
    int x=query(1,0,n,Yma);
    if(x<=n)change(1,0,n,x,n,Yma);
    ans=min(ans,n+max(Xma+Yma,find(1,0,n,Xma,n)));
    for(int i=n;i;i--)
    {
        if(La[a[i]]==i)
        {

            if(!Lb[a[i]])
            {
                if(!Lc[a[i]])break;
                Yma=max(Yma,Lc[a[i]]);
            }
            else if(!Lc[a[i]])Xma=max(Xma,Lb[a[i]]);
            else{
                int x=query(1,0,n,Lc[a[i]]);
                if(x<=Lb[a[i]]-1)change(1,0,n,x,Lb[a[i]]-1,Lc[a[i]]);
            }
        }
        int x=query(1,0,n,Yma);
        if(x<=n)change(1,0,n,x,n,Yma);
        ans=min(ans,i-1+max(Xma+Yma,find(1,0,n,Xma,n)));
    }
    cout<<ans;
}
/*
枚举x
然后就是线段树维护 
*/