算法1
(线段树) $O(n*logn)$
维护区间内被砍了多少树,懒标记f表示这个区间的树是否全部被砍
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define PI acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 6e4+5;
int mod = 1e9 +7;
int n,m,k;
struct node{
int l,r,sum;
bool f;
}tr[maxn];
void pushup(int u){
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u){
if(!tr[u].f) return;
tr[u << 1].sum = tr[u << 1].r - tr[u << 1].l + 1;
tr[u << 1].f = true;
tr[u << 1 | 1].sum = tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1;
tr[u << 1 | 1].f = true;
}
void build(int u,int l,int r){
if(l == r) tr[u] = {l,r,0};
else{
tr[u] = {l,r,0};
int mid = l + r >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
}
}
void modify(int u,int l,int r){
if(tr[u].l >= l && tr[u].r <= r) tr[u].sum = tr[u].r - tr[u].l + 1,tr[u].f = true;
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(mid >= l) modify(u << 1,l,r);
if(mid < r) modify(u << 1 | 1,l,r);
pushup(u);
}
}
void solve(){
cin >> n >> m;
build(1,0,n);
while(m--){
int l,r;
cin >> l >> r;
modify(1,l,r);
}
cout << n + 1 - tr[1].sum << endl;
}
signed main(){
IOS;
solve();
return 0;
}