时间限制：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 3100 200150 300470 471
- 样例输出：
-
298
- 来源：
思路：
我写代码1的时候还不知道线段树的概念，用了一种比较笨的方法，每次对区间内所有数赋值操作。这个题时间复杂度要求不高，能通过。
后来学了一下线段树，用线段树实现的，见代码2。很奇怪的是线段树的时间复杂度并没有显著改善
代码1：
#include#include #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
代码2：
#include#include #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