Thinking Process

solution one

i firstly consider to search the given range directly because of the small range of data. This is one solution but doesn't work in many ocassions.

next solution

i use difference to solve this problem elegantly.
what i need to do is to maintain a difference array. when i recieve a pari (l,r), i need to add 1 to diff[l] as well as sub diff[r+1] and 1. finally restore original array and find how much '1' is. That's all. let's do it!

#include<stdio.h>
int path[100010];
int diff[100010];
int n, m;
int main(){
	scanf("%d%d", &n, &m);
  	for(int i = 0;i <= n;i ++) path[i] = 1; // notice where i starts
  	for(int i = 1;i <= n;i ++) diff[i] = path[i] - path[i - 1]; // notice where i starts
  	
  	for(int i = 0;i < m;i ++) {
    	int l,r;
      	scanf("%d%d", &l, &r);
      	diff[l] += 1;
      	diff[r + 1] -=1;
    }
  	
	path[0] = path[0] + diff[0]; // special occasion
  	for(int i = 1;i <= n; i++) path[i] = path[i - 1] + diff[i];
  	
  	int cnt = 0;
  	for(int i = 0;i <= n;i ++) 
      	if(path[i] == 1) cnt ++;
  	printf("%d", cnt);
}

go on next solution!

trust u have found a question on the second solution that waste plenty of memeory spaces and does't work when given a path length up to $1 0^{9}$ . So i have to find a more effective algorithm.Here is it.
There are many spaces wasted in the 2nd. can we converse some spaces? that's ok! As long as i only save which range of trees should be cut and which range of trees should be saved, then i only need $2 * m$ spaces to sovle the problem.
i use struct to save. 'pos' expresses location and 'num' expresses that +1 or -1 in this location. and +1 represents it should be cut and -1 represents nums in location range begining this location to the next location which num is +1 are all zero, which means these trees are not cut.

struct ty{
	int pos, num;
}a[2*m + 1]

Considering (l,r) is not given me by order, so i have to sort them out by the pos!. and the whole algorithm essense is when meet blue result+=the number of blue! alt
if u cannot see the picture above, u can lick the link below. I hava uploaded on the internet!
(https://img1.imgtp.com/2022/10/02/ZLHPgEeT.png)
i have rearrange the whole process, so let's do it!

#include<stdio.h>
#include<algorithm>
int n, m;
struct ty{
    int pos, num;
}a[210];

bool cmp(ty a, ty b) {
    return a.pos < b.pos;
}

using namespace std;
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m;i ++) {
        int l,r;
        scanf("%d%d", &l, &r);
        a[i].pos = l, a[i].num = 1;
        a[i + m].pos = r + 1, a[i + m].num = -1;
    }
    
    sort(a + 1, a + 2*m + 1, cmp); // must sort because some ranges are interlaced probably
//    for(int i = 1;i <= 2 * m; i ++) printf("a[%d].pos=%d, a[%d].num=%d \n",i ,a[i].pos, i, a[i].num); the line is optional. if you want to know what saved in a, u can run this line 
    int b = 0, cnt = 0;
    for(int i = 1;i <= 2*m; ++i) {
        b += a[i].num;
        if(b == 1 && a[i].num == 1){ // to guarentee b is from 0 to 1 not from 2 to 1, it's important!
            cnt += a[i].pos - a[i - 1].pos;
        } 
            
    }
    cnt += n - a[2 * m].pos + 1;
    printf("%d", cnt);
}

keep on! the fourth!

the fourth is not concerning scale of m or n!it's merge intervals.
when given many intervals, some are interlaced probably. so what we only do is judging if the interval would occupy other intervals or be occupied. How i do?

sort the whole given intervals by left points growing from small to big.
(l,r) means that from l to r this is an interval of no trees
if the next interval,(x,y), x < r, i should merge them. The left point of interval is still l, but the right will be max(r,y) because r greater than y and y greater than r probably.
if not, r - l + 1 is cut and add to cnt(the result) and update (l,r) to (x,y). and loop this. i can get the final right answer.

#include<stdio.h>
#include<algorithm>
#include<math.h>
int n, m;
struct ty{
    int l,r;
}a[210];

bool cmp(ty a, ty b) {
    return a.l < b.l;
}

using namespace std;
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m;i ++) {
        int l,r;
        scanf("%d%d", &a[i].l, &a[i].r);
    }
    sort(a, a + m, cmp);
    int l = a[0].l, r = a[0].r;
    int cnt = n + 1;
    for(int i = 1;i < m;i ++) {
        if(a[i].l < r) {
            r = max(r, a[i].r);
        }
        else {
            cnt -= r - l + 1;
            l = a[i].l;
            r = a[i].r;
        }
    }
  
    cnt -= r - l + 1; // here is essential! because the last intervals should be also added
    printf("%d", cnt);
}

Addition