题目描述
某校大门外长度为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//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//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//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//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 >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，四种解法发完。
（你会几种？_ (:зゝ∠) _）