C. Painting the Fencetime 

没想到前缀和还能这么用

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+50;
int l[maxn],r[maxn];
int cnt_arr[maxn],pre_arr[maxn];
int main(){
    ios::sync_with_stdio(false);
    //cin.tie(0);
    int n,q;
    cin>>n>>q;
    int sum=0,ans=0;
    memset(cnt_arr,0,sizeof(cnt_arr));
    for(int i=1;i<=q;i++){
        cin>>l[i]>>r[i];
        for(int j=l[i];j<=r[i];j++)
            cnt_arr[j]++;
    }
    for(int i=1;i<=q;i++){
        for(int j=l[i];j<=r[i];j++)
            cnt_arr[j]--;
        sum=0;
        for(int j=1;j<=n;j++){
            if(cnt_arr[j]==1)
                pre_arr[j]=pre_arr[j-1]+1;
            else 
                pre_arr[j]=pre_arr[j-1];
            if(cnt_arr[j])
                sum++;
        }
        for(int j=i+1;j<=q;j++)
            ans=max(ans,sum-pre_arr[r[j]]+pre_arr[l[j]-1]);
        for(int j=l[i];j<=r[i];j++)
            cnt_arr[j]++;
    }
    cout<<ans<<endl;
    //system("pause");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注