牛客值周（差分+前缀和，离散）

题目描述
JC内长度为L的马路上有一些值周同学，每两个相邻的同学之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0,1,2,…L，都有一个值周同学。由于水宝宝有用一些区间来和ssy搞事情，所以为了避免这种事走漏风声，水宝宝要踹走一些区域的人。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的人（包括区域端点处的两个人）赶走。你的任务是计算将这些人都赶走后，马路上还有多少个人。

输入描述:
第一行有2个整数L和M，L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含2个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标

输出描述:
1个整数，表示马路上剩余的人的数目。

输入
500 3
150 300
100 200
470 471

输出
298

说明
对于所有的数据，1≤L≤100000000

对于10%的数据，1<=M<=100

对于20%的数据，1<=M<=1000

对于50%的数据，1<=M<=100000

对于100%的数据，1<=M<=1000000

PS：其实这道题目的正解是离散的做法，不过差分+前缀和也可以过，因为这道题目的数据很大，暴力的话毫无疑问是tle的，差分的代码看的时候理解起来有点难度，但是只要自己手动模拟一遍就能很好的理解差分的代码了，差分的话我们只需要对区间端点标记一次就可以了，在最后统计的时候我们就求其前缀和就知道有多少个人符合题目要求，为什么要标记的时候是在y+1那里标记，因为我们查询的区间是[x,y],y+1不在区间里面，所以就这样标记。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e8 + 10;
typedef long long ll;
int a[maxn], dp[maxn];
int main()
{
   
    int n, k;
    while (~scanf("%d%d", &n, &k))
    {
   
        a[0] = 1;
        while (k--)
        {
   
            int x, y;
            scanf("%d%d", &x, &y);
            a[x]--, a[y + 1]++;
        }
        ll ans = 0;
        if (a[0] > 0)
            ans = 1;
        for (int i = 1; i <= n; ++i)
        {
   
            a[i] += a[i - 1];
            if (a[i] > 0)
                ++ans;
        }
        printf("%lld\n", ans);
    }
}

正解——离散

我们把区间端点按照左端点升序排列，如果相同那就右端点升序排列
对于查询的区间我们只需要计算区间的长度，如果区间有重复的判断一下就行
不断地遍历且更新右端点，如果没有重复的就加上这段区间的长度，如果有重复的那就用当前的右端点减去之前的右端点就是新的符合题目的区间

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
struct node
{
   
    int l, r;
    bool operator<(const node x)
    {
   
        if (l != x.l)
            return l < x.l;
        return r < x.r;
    }
} w[maxn];
int main()
{
   
    int n, m;
    while (~scanf("%d%d", &n, &m))
    {
   
        for (int i = 1; i <= m; ++i)
            scanf("%d%d", &w[i].l, &w[i].r);
        sort(w + 1, w + m + 1);
        int ans = w[1].r - w[1].l + 1, cnt = w[1].r;
        for (int i = 2; i <= m; ++i)
        {
   
            if (w[i].l > cnt)
            {
   
                ans += w[i].r - w[i].l + 1;
                cnt = w[i].r;
            }
            else if (w[i].r >= cnt)
            {
   
                ans += w[i].r - cnt;
                cnt = w[i].r;
            }
        }
        printf("%d\n", n - ans + 1);
    }
}

在离散的代码中有一个神奇的操作pair<int, int> a[maxn]; 默认先first升序，后second升序，可以用结构体内嵌比较函数也就是之前的代码，在我们吧数据存进去的时候可以用a[i] = make_pair(l, r);，也可以a[i]={(l,r)};

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
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;
}