【题目描述：】
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
【输入格式：】
输入文件tree.in的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
【输出格式：】
输出文件tree.out包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
输入样例#1： 500 3 150 300 100 200 470 471 输出样例#1： 298
【算法分析：】
使用线段树来维护数轴上的点的状态，作为线段树例题虽然水也有些需要注意的地方
左端点从0开始，建树时叶子节点直接赋成1，
lazy-tag开成bool型表示这个区间被清零.
修改（及标记下传）时不必管要加几或减几，直接把区间清零
由于最后是输出[0, n]的树的数量，直接输出线段树的第一个节点就好，不需要支持查询
【代码：】
1 //校门外的树 2 #include<iostream> 3 #include<cstdio> 4 using namespace std; 5 6 const int MAXN = 10000 + 2; 7 8 int n, m; 9 struct Segment { 10 int sum; 11 bool lazy; 12 }t[MAXN << 2]; 13 14 inline int read() { 15 int x = 0, f = 1; char ch = getchar(); 16 while(ch < '0' || ch > '9') { 17 if(ch == '-') f = -1; 18 ch = getchar(); 19 } 20 while(ch >= '0' && ch <= '9') 21 x = (x << 3) + (x << 1) + ch - 48, ch = getchar(); 22 return x * f; 23 } 24 25 void Build(int o, int l, int r) { 26 if(l == r) t[o].sum = 1; 27 else { 28 int mid = (l + r) >> 1; 29 Build(o << 1, l, mid); 30 Build(o << 1|1, mid + 1, r); 31 t[o].sum = t[o << 1].sum + t[o << 1|1].sum; 32 } 33 } 34 inline void down(int o, int len) { 35 if(!t[o].lazy) return; 36 t[o << 1].sum = 0; 37 t[o << 1|1].sum = 0; 38 t[o << 1].lazy = 1; 39 t[o << 1|1].lazy = 1; 40 t[o].lazy = 0; 41 } 42 void Update(int o, int l, int r, int ul, int ur) { 43 if(ul <= l && r <= ur) { 44 t[o].sum = 0; 45 t[o].lazy = 1; 46 } 47 else { 48 down(o, r - l + 1); 49 int mid = (l + r) >> 1; 50 if(ul <= mid) Update(o << 1, l, mid, ul, ur); 51 if(ur > mid) Update(o << 1|1, mid + 1, r, ul, ur); 52 t[o].sum = t[o << 1].sum + t[o << 1|1].sum; 53 } 54 } 55 56 int main() { 57 n = read(), m = read(); 58 Build(1, 0, n); 59 for(int i = 1; i <= m; ++i) { 60 int l = read(), r = read(); 61 Update(1, 0, n, l, r); 62 } 63 printf("%d\n", t[1].sum); 64 }