学步园

#include <iostream><br /> using namespace std;</p> <p>int wall[10000001]={0}; //开个10000001的数组标记每个byte贴的哪一张海报,只用1...10000000<br /> int *flag;//动态开个海报数量的数组用来标记哪张海报没被覆盖<br /> int n; //n张海报<br /> int sum=0;</p> <p>int main()<br /> {<br /> cin>>n;</p> <p> for(int cnt=1,li=0,ri=0;cnt<=n;++cnt)<br /> {<br /> cin>>li>>ri;<br /> for(int j=li;j<=ri;++j)<br /> {<br /> wall[j]=cnt;<br /> }<br /> }</p> <p> flag=new int[n+1];<br /> memset(flag,0,(n+1)*sizeof(int));</p> <p> for(int cnt=1;cnt<=10000000;++cnt)<br /> {<br /> if(wall[cnt]!=0)<br /> {<br /> flag[wall[cnt]]=1;<br /> }<br /> }</p> <p> for(int cnt=1;cnt<=n;++cnt)<br /> {<br /> if(flag[cnt]!=0)<br /> {<br /> ++sum;<br /> }<br /> }</p> <p> cout<<sum;<br /> delete []flag;<br /> }</p> <p>

描述
数码城正在举行市长选举，城中各处贴满了竞选者的海报，这引起了一些市民的不满。因此城市委员会决定建造一座竞选墙，让参加竞选的人把自己的海报统 一贴到竞选墙上。张贴海报的规则是：
每一个候选人只能张贴一张海报； 
海报的高度和墙的高度一样，而海报的宽度则是任意个 byte 宽（在数码城，byte 是个长度单位）； 
竞选墙被分成很多段，每段的宽度是一个 byte； 
竞选者的海报必须完整地覆盖一串连续的段。 
委员会建立的竞选墙长度为 10,000,000 byte。竞选开始后，候选人可以把他们自己的海报张贴出来。然而，一些候选人却把自己的海报贴在了已经张贴了海报的墙面上，从而盖住了别人的海报。数码 城的人们都很好奇，最后有几个人的海报是可见（部分或全部）的呢？
你的任务就是在海报宽度、位置和张贴顺序这些数据的基础上，找出最终能有几个竞选者的海报能被人们看到。
输入
输入的第一行是一个整数，它表示数据的组数，之后是各组数据。
每组数据的第一行是一个整数 1 <= n <= 10000。后续的 n 行顺序地记录了 n 张海报张贴的位置，每一行有两个整数 li 和 ri，分别是第 i 张海报所占据的最左和最右段号。已知对于每一个 1 <= i <= n，1 <= li <= ri <= 10,000,000。当第 i 份海报张贴后，它会覆盖从 li, li+1,...ri 的所有段。
输出
针对每一组数据，输出最终可以显示出的海报的份数。