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

题目链接：http://codeforces.com/contest/1132/problem/C

       题意是有n个点，m条线段，问用m-2条线段最多可以覆盖多少个点。

       思路就是暴力枚举，但是虽然数据范围不大，但是太暴力也还是过不了的，所以我们可以用前缀和去优化把查询的操作变成O(1)的查询，我们首先记录一下这n个点有多少个点被覆盖了(变量为tot)，然后m^2去枚举要删除的两个线段，对于我们枚举的这两个要删除的线段，会有两种情况，要么相交要么不相交(还有包含的情况)，所以我们只需要查询出有多少个点是只被这两条线段覆盖的点。然后tot减去这些点就是删除这两条线段后被覆盖的点的个数了。对于查询的操作我们用前缀和来优化，我们首先用差分求出每个点被覆盖的次数，然后我们用两个数组分别记录只被覆盖了1次和2次的点的前缀和，那么我们在之后的查询就是O(1)的时间复杂度了，不理解的可以看看呆码。

AC代码：

#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;
}