CF1684F 题解

· · 题解

没看懂题解只能自己口胡

这种多个区间都要满足不是很好处理，考虑 P6773 的套路，预处理出来 limit_i 表示包含 i 的区间，最前面到哪里，这样就将 m 个区间满足条件转化为对于每个 i，limit_i 到 i 之间颜色不能有相同的，同时，limit_i 是随着 i 单调不下降的。

不难发现答案合法的一个必要条件，就是对于任意 i，a_{[limit_i,i-1]} 不能有和 a_i 相同的颜色。而单调不下降这个性质告诉我们，对于 i 的限制，它本身的 limit 的限制是严格不劣于 limit_j(j>i) 对 i 的限制。也就是说，之前说的必要条件是充要的。

现在需要满足的条件变为任意 i，a_{[limit_i,i-1]} 不能有和 a_i 相同的颜色。这个就很套路了，每个颜色开一个 vector，维护它出现的所有位置，然后对于每个 i 求出来 [l_i,r_i] 表示如果 i 没被子段选择，那么 [l_i,r_i] 都需要被子段选择，你需要求最短子段满足所有 i 的限制。

考虑双指针统计答案，每次移动相当于是取消/加入 i 的限制，需要查询的是当前区间是否满足所有限制，线段树维护所有限制的 l 的最小值和 r 的最大值，然后和当前区间比较即可。

#include<iostream>
#include<cstdio>
#include<map>
#include<set>
#include<vector>
using namespace std;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
const int N=2e5+5;
struct tree
{
    int l,r,minn,maxx;
}t[N*4];
int n,L[N],R[N],a[N],limit[N],m;
void pushup(int k)
{
    t[k].minn=min(t[k*2].minn,t[k*2+1].minn);
    t[k].maxx=max(t[k*2].maxx,t[k*2+1].maxx);
}
void build(int k,int l,int r)
{
    t[k].l=l;t[k].r=r;
    if(l==r)
    {
        t[k].minn=L[l];
        t[k].maxx=R[l];
        return;
    }
    int mid=l+r>>1;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    pushup(k);
}
void change(int k,int x,int v)
{
    if(t[k].l==t[k].r)
    {
        if(v) t[k].minn=n+1,t[k].maxx=0;
        else t[k].minn=L[x],t[k].maxx=R[x];
        return;
    }
    if(x<=t[k*2].r) change(k*2,x,v);
    else change(k*2+1,x,v);
    pushup(k);
}
multiset<int> s;
map<int,int> mp;
int tot;
int getid(int x)
{
    if(!mp[x]) mp[x]=++tot;
    return mp[x];
}
vector<int> v[N],v2[N];
bool check(int l,int r)
{
//  cout<<"chk"<<l<<' '<<r<<" "<<t[1].minn<<" "<<t[1].maxx<<endl; 
    return l<=t[1].minn&&t[1].maxx<=r;
}
void solve()
{
    tot=0;
    mp.clear();
    s.clear();
    n=read();m=read();
    for(int i=1;i<=n;i++)
    v[i].clear(),v2[i].clear();
    for(int i=1;i<=n;i++)
    a[i]=read(),a[i]=getid(a[i]),v2[a[i]].push_back(i);
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        v[x].push_back(x);
        v[y+1].push_back(-x);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<v[i].size();j++)
        if(v[i][j]>0) s.insert(v[i][j]);
        else s.erase(s.find(-v[i][j]));
        if(s.empty()) limit[i]=0,L[i]=n+1,R[i]=0;
        else limit[i]=(*s.begin());
    }
    for(int i=1;i<=n;i++)
    {
        if(limit[i]==0)
        {
//           cout<<i<<' '<<L[i]<<" "<<R[i]<<endl;
            continue;
        }
        if(limit[i]==i)
        {
            L[i]=n+1;
            R[i]=0;     
        }
        else
        {
            int l=0,r=v2[a[i]].size()-1;
            L[i]=n+1,R[i]=0;
            while(l<=r)
            {
                int mid=l+r>>1;
                if(v2[a[i]][mid]>=limit[i]) L[i]=v2[a[i]][mid],r=mid-1;
                else l=mid+1;
            }
            if(L[i]>=i) L[i]=n+1;
            l=0,r=v2[a[i]].size()-1;
            while(l<=r)
            {
                int mid=l+r>>1;
                if(v2[a[i]][mid]<i) R[i]=v2[a[i]][mid],l=mid+1;
                else r=mid-1;
            }
            if(R[i]<limit[i]) R[i]=0;
        }
//       cout<<i<<' '<<L[i]<<" "<<R[i]<<endl;
    }
    build(1,1,n);
    int ans=n;
    for(int l=1,r=0;l<=n;l++)
    {
        while(r<n&&!check(l,r)) r++,change(1,r,1);
        if(check(l,r)) ans=min(ans,max(0,r-l+1));
//       cout<<l<<' '<<r<<endl;
        change(1,l,0);
    }
    cout<<ans<<endl;
}
int main()
{
//  freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout); 
    int T=read();
    while(T--) solve();
    return 0;
}

/*
1 5 2
0 5 4 9 4 
1 5
3 4
lgsblgsb
*/