Time Limit: 10 Sec Memory Limit: 256 MB
Description
Bytetown城市要进行市长竞选，所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理，城市委 员 会为选民准备了一个张贴海报的electoral墙。张贴规则如下： 1．electoral墙是一个长度为N个单位的长方形，每个单位记为一个格子； 2．所有张贴的海报的高度必须与electoral墙的高度一致的； 3．每张海报以“A B”表示，即从第A个格子到第B个格子张贴海报； 4．后贴的海报可以覆盖前面已贴的海报或部分海报。 现在请你判断，张贴完所有海报后，在electoral墙上还可以看见多少张海报。
Input
第一行： N M 分别表示electoral墙的长度和海报个数 接下来M行: Ai Bi 表示每张海报张贴的位置
Output
输出贴完所有海报后，在electoral墙上还可以看见的海报数。 1 0<= N <= 10000000 1<=M<=1000 1<= Ai <= Bi <=10000000 所有的数据都是整数。数据之间有一个空格
Sample Input
100 5 1 4 2 6 8 10 3 4 7 10
Sample Output
4
题解
我们将Ai,Bi这条线段拆成两个点Ai和Bi+1，在这两个点之间的所有的点都有i这个编号的海报。编号越大放在越前面，没遇到x这个点，都有取出当前的最大编号，并且带插入和删除的，那么就建一个大根堆，维护当前最大编号就可以了。
代码如下
#include<queue> #include<cstdio> #include<algorithm> using namespace std; int n,m,hsh[1005],Ans; bool vis[1005]; priority_queue<int> hep; struct xcw{ int x,id;bool f; bool operator <(const xcw b)const{return x<b.x;} }a[2005]; int main(){ #ifndef ONLINE_JUDGE freopen("prob.in","r",stdin); freopen("prob.out","w",stdout); #endif scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int L,R;scanf("%d%d",&L,&R); a[i*2-1]=(xcw){L,i,1},a[i*2]=(xcw){R+1,i,0}; } sort(a+1,a+1+2*m); for(int i=1,j=1;i<=n;i++){ while(a[j].x==i&&j<=2*m){ vis[a[j].id]=a[j].f; if(vis[a[j].id]) hep.push(a[j].id); j++; } while(!hep.empty()&&!vis[hep.top()]) hep.pop(); if(!hep.empty()) hsh[hep.top()]=1; } for(int i=1;i<=m;i++) Ans+=hsh[i]; printf("%d\n",Ans); return 0; }