题解：CF2162H Beautiful Problem

· · 题解

思路

若一个区间被另一个区间完全包含，则这个区间没有任何作用，我们可以去掉它，这是不难发现的。

首先发现对于一个 x，这个式子的要求就是给出某些区间，这个区间里的数要么都 \le x，要么都 \ge x。

我们定义一个所有数都 \le x 为小区间，所有数都 \ge x 的大区间。

然后对于一个位置，有 4 种可能。分别是只被小区间覆盖，只被大区间覆盖，同时被两种区间覆盖，不被任何区间覆盖。

我们先考虑没有第 4 种位置的做法。

假设现在有 a 个比 x 小的数，b 个比 x 大的数，然后我们要求有 p_1 个位置为类型 1，p_2 个位置为类型 2，剩下的位置都是类型 3。

那么当且仅当 a\le p_1,b\le p_2 的时候是可行的。因为比方说 a>p_1 了，那么剩下的 <x 的数你没有地方放，因为类型 3 的位置必须放 x。

那么现在加上类型 4 的位置，设它有 p_4 个，那么要求就变为了 \max(0,a-p_1)+\max(0,b-p_2)\le p_4 才可行。这相当于把多出来的数放在没有任何要求的位置上。

所以说，我们希望在 p_1 确定时，p_2 尽可能大。于是设 f_{i,j,0/1} 表示前 i 个区间，已经有 j 个位置为类型 1，最后一个区间是大区间还是小区间时，最多能有多少个位置为类型 2。

但是你发现有可能 i 区间和 i-2 区间可能也有交，那我这样 dp 不就错了吗？但是注意到这种情况下，如果你中间的颜色和两端的不同，那把这个 i-2,i-1,i 这三个区间弄成同一种一定不劣。也就是说，不合法状态一定不优，会被覆盖掉，所以不需要管这种情况。

然后直接用上面的方法对于每个 x 进行判断即可。

代码

#include<bits/stdc++.h>
#define int long long
#define N 2005
#define mod 998244353
#define pii pair<int,int>
#define x first
#define y second
#define pct __builtin_popcount
#define mpi make_pair
#define inf 2e18
using namespace std;
int T=1,n,m,cnt,a[N],f[N][N][2];
pii b[N];
bool st[N];
void solve(int cs){
    if(!cs)return;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st[i]=0;
    }
    for(int i=1;i<=m;i++){
        cin>>b[i].x>>b[i].y;
    }
    sort(b+1,b+m+1);
    cnt=0;
    int mx=0;
    for(int i=1;i<=m;i++){
        if(mx>=b[i].y)continue;
        mx=max(mx,b[i].y);
        b[++cnt]=b[i];
    }
    m=cnt;
    int free=0;
    for(int i=1;i<=m;i++){
        for(int j=b[i].x;j<=b[i].y;j++){
            st[j]=1;
        }
    }
    for(int i=1;i<=n;i++){
        if(!st[i])free++;
    }
    for(int j=0;j<=n;j++){
        f[1][j][0]=f[1][j][1]=-inf;
    }
    f[1][0][0]=b[1].y-b[1].x+1;
    f[1][b[1].y-b[1].x+1][1]=0;
    for(int i=2;i<=m;i++){
        int len=b[i].y-b[i].x+1;
        int cap=0;
        if(b[i-1].y>=b[i].x)cap=b[i-1].y-b[i].x+1;
        for(int j=0;j<=n;j++){
            f[i][j][0]=f[i][j][1]=-inf;
        }
        for(int j=0;j<=n;j++){
            int &v0=f[i][j][0],&v1=f[i][j][1];
            v0=max(v0,f[i-1][j][0]+len-cap);
            if(j+cap<=n)v0=max(v0,f[i-1][j+cap][1]+len-cap);
            if(j>=len-cap)v1=max(v1,f[i-1][j-(len-cap)][0]-cap);
            if(j>=len-cap)v1=max(v1,f[i-1][j-(len-cap)][1]);
        }
    }
    for(int x=1;x<=n;x++){
        int s=0,b=0;
        for(int i=1;i<=n;i++){
            if(a[i]<x)s++;
            if(a[i]>x)b++;
        }
        bool flag=0;
        for(int i=0;i<=n;i++){
            int t1=max(0ll,s-i),t2=max(0ll,b-max(f[m][i][0],f[m][i][1]));
            if(t1+t2<=free){
                flag=1;
                break;
            }
        }
        cout<<flag;
    }
    cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
//  init(1e5);
    for(int cs=1;cs<=T;cs++){
        solve(cs);
    }
    // cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
    return 0;
}