C. Painting the Fence

time limit per test2 seconds
memory limit per test256 megabytes

You have a long fence which consists of n sections. Unfortunately, it is not painted, so you decided to hire q painters to paint it. i-th painter will paint all sections x such that li≤x≤ri.

Unfortunately, you are on a tight budget, so you may hire only q−2 painters. Obviously, only painters you hire will do their work.

You want to maximize the number of painted sections if you choose q−2 painters optimally. A section is considered painted if at least one painter paints it.

Input
The first line contains two integers n and q (3≤n,q≤5000) — the number of sections and the number of painters availible for hire, respectively.

Then q lines follow, each describing one of the painters: i-th line contains two integers li and ri (1≤li≤ri≤n).

Output
Print one integer — maximum number of painted sections if you hire q−2 painters.

Examples
inputCopy
7 5
1 4
4 5
5 6
6 7
3 5
outputCopy
7
inputCopy
4 3
1 1
2 2
3 4
outputCopy
2
inputCopy
4 4
1 1
2 2
2 3
3 4
outputCopy
3
题意：输入一个n和q，n表示你的篱笆被分成n部分，q表示你要请的工人个数，然后q行，第i行表示第i个工人可以修复的区间范围，问你，由于资金问题你只能能得起q-2个工人，怎样使得这q-2个工人维修的区间最大化。
思路：这题看了别人的题解自己没有想出来，然后自己写过了，然后有很多值得学习的地方，就写了这篇博客。
首先由于n取值在[3,5000],所以O(n^2)的算法是可行的，暴力一点我们枚举所有可能去掉的两个人，然后更新最优答案。这里有个小技巧，怎么样模拟去掉某个工人，因为我们发现工人的维修范围是在一个区间，那么我们给所有的点计数，去掉某个工人只需要把他对应的区间计数减掉就行了。有了这个小技巧我们可以开始枚举了，首先枚举去掉一个工人，然后计数去掉这个工人后可以维修的区间，然后再去掉一个人，可以发现第二个去掉的这个人他的维修区间是别人维修不了的才会影响答案，也就是他维修区间的计数 = 1，因为有多个区间要这样计算，所以可以先用前缀和计算出所以区间计数为1的和，然后用sum - 当前工人维修区间为1的部分就行了。
代码:

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

const int maxn = 5e5 + 100;
int cnt[maxn],l[maxn],r[maxn],pres[maxn];//计数，左右区间，前缀和
int main(){
    int n,q;cin>>n>>q;
    for(int i=1;i<=q;i++){
        cin>>l[i]>>r[i];
        for(int j=l[i];j<=r[i];j++)cnt[j]++;//计数
    }
    int ans = 0;
    for(int i=1;i<=q;i++){//枚举去掉的工人
        int sum = 0;
        for(int j=l[i];j<=r[i];j++)cnt[j]--;//去掉工人
        memset(pres,0,sizeof(pres));
        for(int j=1;j<=n;j++){
            if(cnt[j] == 1){
                pres[j] += pres[j-1] + cnt[j];
            }else{
                pres[j] = pres[j-1];
            }
            if(cnt[j])sum++;//剩下的区间
        }
        for(int k=i+1;k<=q;k++){//枚举去掉第二个工人
            ans = max(ans,sum - (pres[r[k]] - pres[l[k]-1]));//只需要去掉他维修部分= 1的部分就行
        }
        for(int j=l[i];j<=r[i];j++)cnt[j]++;//恢复这个工人
    }
    cout<<ans<<endl;
}