题目链接：http://codeforces.com/problemset/problem/1132/C
题目大意：就是有个n长的栅栏，然后每个油漆工可以染的区域不同
给你q让你选出q-2个人使得被染色的栅栏最多

思路：Q的范围允许O(n*n)复杂度，先预处理每个格子被覆盖非0次，被覆盖1次，被覆盖2次的情况，再暴力枚举去掉哪两条就ok，假如去掉X和Y两条，那么覆盖数量减少为X和Y交集部分的覆盖2次的格子数加上X和Y部分并集的覆盖1次的格子数，这些通过前缀和方便求出来。

对于并集的求法，并不需要求并集。因为他们的交集覆盖了至少为2次。所以把这两个直接减去就可以了。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int sum[5005], f[5005], one[5005], tow[5005];
int L[5005], R[5005];

int fun(int i, int j){
    if(L[i]>L[j]){
        swap(i, j);
    }
    if(L[j]>R[i]){
        return 0;
    }
    int t=min(R[i], R[j]);

    return max(0, tow[t]-tow[L[j]-1]);

}

int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    for(int i=1; i<=q; i++){
        scanf("%d%d", &L[i], &R[i]);
        sum[L[i]]++, sum[R[i]+1]--;
    }
    for(int i=1; i<=n; i++){
        sum[i]+=sum[i-1];

        f[i]=f[i-1];
        one[i]=one[i-1];
        tow[i]=tow[i-1];
        if(sum[i]){
            f[i]+=1;
        }
        if(sum[i]==1){
            one[i]++;
        }
        if(sum[i]==2){
            tow[i]++;
        }
    }
    LL ans=0;
    for(int i=1; i<=q; i++){
        for(int j=i+1; j<=q; j++){
            LL s=f[n];

            s-=fun(i, j);//交集
            s-=(one[R[i]]-one[L[i]-1]);
            s-=(one[R[j]]-one[L[j]-1]);
            ans=max(s, ans);
        }
    }
    printf("%lld\n", ans);

	return 0;
}