题目描述
某校大门外长度为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
说明
NOIP2005普及组第二题
对于20%的数据，区域之间没有重合的部分；
对于其它的数据，区域之间有重合的情况。
分析
四种解法，不解释
#include<bits/stdc++.h> //1层----模拟流
using namespace std;
int n,m,ans;
bool a[11000];int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c) && c!='-') c=getchar();
if(c=='-') f=-1,c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*f;
}int main()
{
n=read()+1;m=read();
while(m--)
{
int l=read(),r=read();
for(int i=l;i<=r;++i)
a[i]=1; //表示已被砍
}
for(int i=0;i<=n;++i)
if(a[i]) ++ans; printf("%d\n",n-ans); return 0;
} 这里是分割线
#include<bits/stdc++.h> //2层----忘了是什么算法来着，反正比模拟高级
using namespace std;
int n,m,ans;
int a[11000],f[11000];int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c) && c!='-') c=getchar();
if(c=='-') f=-1,c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*f;
}int main()
{
n=read()+1;m=read(); //代码需要，就+1了，下同
while(m--)
{
int l=read()+1,r=read()+1;
++a[l];--a[r+1];
} for(int i=1;i<=n;++i)
{
f[i]=f[i-1]+a[i];
if(f[i]) ++ans; //被砍过，ans++
} printf("%d\n",n-ans); return 0;
}这里是分割线
#include<bits/stdc++.h> //3层----树状数组(比线段树好打一些)
using namespace std;
int n,m,f[11000],ans;
/* 本代码以树状数组区间加，单点查询为模板 */int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c) && c!='-') c=getchar();
if(c=='-') f=-1,c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*f;
}int lowbit(int x)
{
return x&(-x);
}void update(int i,int x)
{
for(;i<=n;i+=lowbit(i))
f[i]+=x;
}bool query(int i)
{
int res=0;
for(;i;i-=lowbit(i))
if(f[i]) res+=f[i];
return res;
}int main()
{
n=read()+1;m=read(); //注意题目中的树范围是0~n，
//树状数组的操作是从1开始的，所以n++
while(m--)
{
int l=read()+1,r=read()+1; //同上+1
update(l,1);
update(r+1,-1);
} for(int i=1;i<=n;++i)
if(query(i)) ++ans; //被砍过，ans++ printf("%d\n",n-ans); return 0;
}这里是分割线
#include<bits/stdc++.h> //4层----线段树
using namespace std;
int n,m,sum[41000];//姑且写个读入优化吧，虽说其实用不着
int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c) && c!='-') c=getchar();
if(c=='-') f=-1,c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*f;
}void buildtree(int k,int l,int r)
{
if(l==r){ sum[k]=1; return ;}
if(l>r) return ;
int mid=l+r>>1;
buildtree(k*2,l,mid);
buildtree(k*2+1,mid+1,r);
sum[k]=sum[k*2]+sum[k*2+1];
}void update(int k,int l,int r,int L,int R)
{
if(l>R || r<L || !sum[k]) return ; //不包含直接退
if(L<=l && r<=R) //全包含sum改0
{
sum[k]=0;
return ;
} int mid=l+r>>1;
update(k*2,l,mid,L,R);
update(k*2+1,mid+1,r,L,R);
sum[k]=sum[k*2]+sum[k*2+1]; //更新sum[father];
}int main()
{
n=read();m=read();
buildtree(1,0,n);
while(m--)
{
int l,r;
l=read();r=read();
update(1,0,n,l,r);
} printf("%d\n",sum[1]);
return 0;
} --all by Mr Zhang
ok，四种解法发完。
（你会几种？_ (:зゝ∠) _）
