题解 | 剩下的树

#include<bits/stdc++.h>
#define int long long
#define _for(i, a, b) for(int i = a;i < b;++i)
#define _rep(i, a, b) for(int i = a;i <= b;++i)
int readll(){int x; scanf("%lld", &x); return x;}
using namespace std; 
#define INF 0x3f3f3f3f

typedef struct node{
	int left, right;
	node *next;
} *linklist;


signed main(){
	int L, M;
	cin>>L>>M;
	linklist pnode = new node;
	pnode -> next = NULL;
	while(M--){
		node * temp = new node;
		temp -> left = readll();
		temp -> right = readll();
		temp -> next = NULL;
		if(pnode -> next == NULL){
			pnode -> next = temp;
			continue;
		}
		node * t = pnode -> next;
		node * p = pnode;
		while(t != NULL && t -> left < temp -> left){
			p = t;
			t = t -> next;
		}
		p -> next = temp;
		temp -> next = t;
	}//insert
	
	node * temp = pnode -> next;
	
	
	/*
	cout<<endl;
	while(temp != NULL){
		cout<<temp -> left<<' '<<temp -> right<<endl;
		temp = temp -> next;
	}//traversal
	*/
	
	temp = pnode -> next;
	while(temp -> next != NULL){
		node * t = temp -> next;
		if(temp -> right >= t -> left){
			if(temp -> right < t -> right)	temp -> right = t -> right;
			temp -> next = t -> next;
			delete t;
			continue;
		}
		temp = t;
	}//merge
	
	/*
	cout<<endl;
	temp = pnode -> next;
	while(temp != NULL){
		cout<<temp -> left<<' '<<temp -> right<<endl;
		temp = temp -> next;
	}//traversal
	*/
	
	
	int total = 0;
	temp = pnode -> next;
	while(temp != NULL){
		total += (temp -> right) - (temp -> left) + 1;
		temp = temp -> next;
	}
	cout<<L + 1 - total; 
	return 0;
}

建一个链表实现插入合并后，再把所有并区间累加起来减掉就好了