差分+离散化

//先差分，再前缀和

#include<bits/stdc++.h>
using namespace std;
namespace{
    template<typename T>
    inline void read(T &s){
        T f=1;s=0;char ch=getchar();
        for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar()) s=(s<<1)+(s<<3)+(ch^48);
        s*=f;
    }
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int const N=10005;
int main(){
    int l,m,a[N],cnt=0;
    cin >> l >> m;
    memset(a,0,sizeof(a)); //差分之后数组的值 
    a[0]=1;      //将a[0]的值精确为差分之后的值 
    for(int i,j;m--;){
        cin >> i >> j;
        a[i] -= 1;
        a[j+1] +=1;
    }
    if(a[0]==1) cnt++;
    for(int i=1;i<=l;i++){
        a[i]+=a[i-1];
        if(a[i]==1)
          cnt++;
    }
    cout << cnt << endl;
    return 0; 
}

//也可以用离散化做
//离散化

struct L{
    int pos,num;   //保存位置pos 用数字标记(区分)左括号和右括号） 
}a[205];
bool cmp(L const &a,L const &b){
    return a.pos < b.pos;
}
int main(){
    fio;
    int l,m;
    read(l);read(m);
    for(int i=1;i<=m;++i){
        int x1,x2;
        read(x1);read(x2);
        if(x1>x2) swap(x1,x2);
        a[i*2-1].pos =x1;
        a[i*2-1].num =1;
        a[i*2].pos =x2+1;
        a[i*2].num =-1;
    }
    sort(a+1,a+2*m+1,cmp);
    int sum=0,cnt=0;
    for(int i=1;i<=2*m;++i){
        sum +=a[i].num + a[i-1].num ;
        if(sum ==1&&a[i].num ==1){
            cnt+=a[i].pos -a[i-1].pos ;
        }
    }
    cnt+=l-a[2*m].pos +1;
    cout << cnt << endl;
    return 0;
}