算法1
(暴力枚举) $O(nm)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n,m;
bool vis[N];
int main() {
cin >> n >> m;
while(m -- ) {
int l,r;
cin >> l >> r;
for (int i = l; i <= r; i ++) vis[i] = true;
}
int res = 0;
for (int i = 0; i <= n; i ++) {
if(!vis[i]) res++;
}
cout << res << endl;
return 0;
}
算法2
(线段树) $O(mlogn)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
using namespace std;
int n,m,x,y;
struct node
{
int l,r,val;
bool flag;
}tr[4 * N];
void pushdown(int u)
{
tr[u<<1].flag=true;
tr[u<<1|1].flag=true;
tr[u<<1].val=0;
tr[u<<1|1].val=0;
}
void pushup(int u) {
tr[u].val=tr[u<<1].val+tr[u<<1|1].val;
}
void build(int u,int l,int r)
{
tr[u].l=l;tr[u].r=r;
tr[u].flag=false;
if(l==r)
{
tr[u].val=1;
return;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r)
{
if(tr[u].l==l&&tr[u].r==r)
{
tr[u].val=0;
tr[u].flag=true;
return;
}
if(tr[u].flag) pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(l>mid) modify(u<<1|1,l,r);
else if(r<=mid) modify(u<<1,l,r);
else
{
modify(u<<1,l,mid);
modify(u<<1|1,mid+1,r);
}
tr[u].val=tr[u<<1].val+tr[u<<1|1].val;
}
int main()
{
scanf("%d%d",&n,&m);
build(1,0,n);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
modify(1,x,y);
}
printf("%d\n",tr[1].val);
return 0;
}
dalao