值周

思路

最开始懒得离散化直接开1e8的数组用差分做，提交发现能ac，良心出题人啊给了这么大的空间

就说明这个位置有人，因为可能多次赶一个地方的人，所以差分数组有可能是负数

如果没学过差分的同学可以去看看这篇大佬的博客

正解应该是离散，计算被清除的区间长度，总长度减掉区间长度加一就是答案。维护终点即可。为什么加一就不用说了吧（长度为L的区间位置0，1，2.。。L有人，加起来L+1个人）

这里要注意的就是 0 这个位置也是有一个人的，不要忘记了加。

直接差分代码

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define pll pair<ll,ll>
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 10005;
#define stop system("pause")
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int dp[100000005];
int main(){
    int l = read(),m = read();
    dp[0] = 1;
    while(m--){
        int x = read(),y = read();
        dp[x]--;
        dp[y+1]++;
    }
    ll ans = 0;
    if(dp[0] > 0) ans = 1;
    for(int i = 1;  i <= l ; ++i){
        dp[i] += dp[i-1];
        if(dp[i] > 0) ++ans;
    }
    cout<<ans<<endl;
}

离散 代码

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define pll pair<ll,ll>
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 1e6+7;
#define stop system("pause")
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
pair<int, int> a[maxn]; //先first升序，后second升序

int main() {
    int n = read(), m = read();
    int l, r;
    for (int i = 1; i <= m; ++i)
        l = read(), r = read(), a[i] = make_pair(l, r);
    sort(a + 1, a + 1 + m);
    int sum = a[1].second - a[1].first + 1,ed = a[1].second;
    for (int i = 2; i <= m; ++i)
        if (a[i].first > ed) {
            sum += a[i].second - a[i].first + 1;
            ed = a[i].second;
        }
        else if (a[i].second >= ed) {
            sum += a[i].second - ed;
            ed = a[i].second;
        }
    cout<<n-sum+1;
    return 0;
}