时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：5791
解决：2649
- 题目描述：
有一个长度为整数L(1<=L<=10000)的马路，可以想象成数轴上长度为L的一个线段，起点是坐标原点，在每个整数坐标点有一棵树，即在0,1,2，...，L共L+1个位置上有L+1棵树。
现在要移走一些树，移走的树的区间用一对数字表示，如 100 200表示移走从100到200之间（包括端点）所有的树。
可能有M(1<=M<=100)个区间，区间之间可能有重叠。现在要求移走所有区间的树之后剩下的树的个数。
- 输入：
两个整数L(1<=L<=10000)和M(1<=M<=100)。
接下来有M组整数，每组有一对数字。
- 输出：
可能有多组输入数据，对于每组输入数据，输出一个数，表示移走所有区间的树之后剩下的树的个数。
- 样例输入：
500 3
100 200
150 300
470 471
- 样例输出：
298
思路：
我写代码1的时候还不知道线段树的概念，用了一种比较笨的方法，每次对区间内所有数赋值操作。这个题时间复杂度要求不高，能通过。
后来学了一下线段树，用线段树实现的，见代码2。很奇怪的是线段树的时间复杂度并没有显著改善
代码1：
#include <stdio.h>
#include <string.h> #define N 10000 int main(void)
{
int L, M;
int moved[N+1];
int i, j;
int begin, end; while (scanf("%d%d", &L, &M) != EOF)
{
memset(moved, 0, (N+1)*sizeof(int));
for (i=0; i<M; i++)
{
scanf("%d%d", &begin, &end);
for (j=begin; j<=end; j++)
moved[j] = 1;
}
int count = 0;
for (j=0; j<=L; j++)
count += moved[j];
printf("%d\n", L+1-count);
} return 0;
}
/**************************************************************
Problem: 1088
User: liangrx06
Language: C
Result: Accepted
Time:50 ms
Memory:912 kb
****************************************************************/
代码2：
#include <stdio.h>
#include <limits.h> #define N 10001 int seg[4*N]; void pushdown(int i)
{
if (seg[i] != -1)
{
seg[2*i] = seg[i];
seg[2*i+1] = seg[i];
seg[i] = -1;
}
} void update(int k, int i, int b, int e, int l, int r)
{
if (b > r || e < l)
return;
if (l <= b && e <= r)
{
seg[i] = k;
return;
}
pushdown(i);
update(k, 2*i, b, (b+e)/2, l, r);
update(k, 2*i+1, (b+e)/2+1, e, l, r);
} int getsum(int i, int b, int e)
{
if (seg[i] == -1)
return getsum(2*i, b, (b+e)/2) + getsum(2*i+1, (b+e)/2+1, e);
if (seg[i] == 1)
return e-b+1;
else
return 0;
} int main(void)
{
int n, i, m;
int l, r; while (scanf("%d%d", &n, &m) != EOF)
{
for (i=0; i<4*N; i++)
seg[i] = -1;
update(1, 1, 0, n, 0, n); for (i=0; i<m; i++)
{
scanf("%d%d", &l, &r);
update(0, 1, 0, n, l, r);
}
printf("%d\n", getsum(1, 0, n));
} return 0;
}
/**************************************************************
Problem: 1088
User: liangrx06
Language: C
Result: Accepted
Time:40 ms
Memory:1068 kb
****************************************************************/