Educational Codeforces Round 61 (Rated for Div. 2) C. Painting the Fence(思维+前缀和)

#include <bits/stdc++.h>
#define maxn 5005
using namespace std;
typedef pair<int,int> p;
int n,m;
int pre[maxn],a[maxn],b[maxn];
vector<p> v;

int main()
{
    scanf("%d%d",&n, &m);
    for(int i=0;i<m;i++){
        int a, b;
        scanf("%d%d",&a,&b);
        pre[a] ++;
        pre[b + 1] --;
        v.push_back(p(a, b));
    }
    int tot = 0;
    for(int i=1;i<=n;i++){
        pre[i] += pre[i-1];
        if(pre[i]) tot ++;
        a[i] = a[i-1];
        b[i] = b[i-1];
        if(pre[i] == 1) a[i] ++;
        if(pre[i] == 2) b[i] ++;
    }
    sort(v.begin(), v.end());
    int ans = 0;
    for(int i=0;i<m;i++){
        for(int j=i+1;j<m;j++){
                int cnt = 0;
            if(v[i].second >= v[j].first){
                if(v[i].second >= v[j].second){
                    cnt += a[v[i].second] - a[v[i].first - 1];
                    cnt += b[v[j].second] - b[v[j].first - 1];
                }
                else{
                    cnt += b[v[i].second] - b[v[j].first - 1];
                    cnt += a[v[j].first - 1] - a[v[i].first - 1];
                    cnt += a[v[j].second] - a[v[i].second];
                }
            }
            else{
                cnt += a[v[i].second] - a[v[i].first - 1];
                cnt += a[v[j].second] - a[v[j].first - 1];
            }
            ans = max(ans, tot - cnt);
        }
    }
    printf("%d\n", ans);
    return 0;
}