竞选海报问题,用C语言实现!急
描述
数码城正在举行市长选举，城中各处贴满了竞选者的海报，这引起了一些市民的不满。因此城市委员会决定建造一座竞选墙，让参加竞选的人把自己的海报统 一贴到竞选墙上。张贴海报的规则是：
每一个候选人只能张贴一张海报；
海报的高度和墙的高度一样，而海报的宽度则是任意个 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 的所有段。
输出
针对每一组数据，输出最终可以显示出的海报的份数。

PS:本人一点思路没有,这个问题要怎样实现呢,数据结构我们只学了数组广义表 线性表 栈队列,不知道怎样解决,高手给个实现代码,或者提供下思路也行.

[解决办法]
似乎比较慢,差不多是N * N的复杂度.
没有记录显示海报的编号.

C/C++ code

// 竞选海报墙纸.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>#include <vector>#include <map>#include <list>using namespace std;typedef unsigned int size_type;void add(map<size_type,size_type> & v,pair<size_type,size_type> pSource){    if(pSource.second <= pSource.first)        return ;    pair<size_type,size_type> p1(0,0),p2(0,0);    size_type iNum = 0;    for(map<size_type,size_type>::iterator p = v.begin();p != v.end();){        if(p->second <= pSource.first){            ++ p;            continue;        }        if(pSource.second <= p->first)            break;        if(iNum ++)            p2 = *p;        else            p1 = *p;                v.erase(p ++);    }    v.insert(pSource);    if(iNum){//有重复部分        if(iNum == 1){//只有一个重叠            if(p1.first < pSource.first)//原有的前部分没有被覆盖                v.insert(pair<size_type,size_type>(p1.first,pSource.first));            if(pSource.second < p1.second)//原有的后半部分没有被覆盖                v.insert(pair<size_type,size_type>(pSource.second,p1.second));        }        else{//有两个部分以上被覆盖            if(p1.first < pSource.first)//原有的前部分没有被覆盖                v.insert(pair<size_type,size_type>(p1.first,pSource.first));            if(pSource.second < p2.second)//原有的后半部分没有被覆盖                v.insert(pair<size_type,size_type>(pSource.second,p2.second));        }    }}int _tmain(int argc, _TCHAR* argv[]){    map<size_type,size_type> m;    size_type n ;    cin >> n;    for(size_type x = 0; x < n;++ x){        size_type a,b;        cin>> a >> b;        add(m,pair<size_type,size_type> (a,b));    }    for(map<size_type,size_type>::iterator p = m.begin();p != m.end();++p){        cout<<p->first<<"---"<<p->second<<" ";    }    cout<<endl;    return 0;}
[解决办法]
C/C++ code
  #include <iostream>using namespace std;#define LEN 20000#define NO_POSTER -2 //无海报#define MIX_POSTER -1 //混合(间断)海报#define NO_FLAG 0//线段树的静态表示,左边界,右边界,标志域,结点对应海报编号,海报能否看见的标记数组,结点数量,最终能看见的海报数量int left_bound[LEN],right_bound[LEN],flag[LEN],poster[LEN],ref[LEN],node_num,count_poster;//clear(int index),更新poster[index],flag[index],flag[left_child[index]],flag[right_child[index]]void clear(int index){    poster[index]=flag[index];    flag[2*index]=flag[index];    flag[2*index+1]=flag[index];    flag[index]=NO_FLAG;}//创建线段树void construct(int left,int right,int num=1){    ++node_num;    left_bound[num]=left;    right_bound[num]=right;    poster[num]=NO_POSTER;    if(left+1<right)    {        int mid=(left+right)/2;        construct(left,mid,2*num);        construct(mid,right,2*num+1);    }}//贴海报void insert(int index,int left,int right,int num){    if(flag[index]!=NO_FLAG) //如果有标志域,说明被完全覆盖过,所以更新自己的海报信息与孩子的标志域******PS:标志域的作用就是当前结点与之下子结点信息一致时,免去一次性全部更新的浪费                            //先用标志域存储起来,下次需要用时临时更新需要的结点获得信息..看下一条注释!    {        clear(index);    }    if(left==left_bound[index]&&right_bound[index]==right)//例如: 如果某结点完全覆盖,那么它的子结点与该结点继承同一海报,所以这时候用标志域比用poster[]记录要有效得多！看下一条注释！    {        flag[index]=num;        return;    }    else//如果没有完全覆盖,那么就不能标志当前结点的flag,因为子结点与该结点没有相同的特征,子结点只是零散的覆盖该结点，所以这时只要修改poster[index]为混合标记就可以了.    {        poster[index]=MIX_POSTER;        int mid=(left_bound[index]+right_bound[index])/2;        if(left<mid&&right<=mid)        {            insert(2*index,left,right,num);        }        if(left<mid&&right>mid)        {            insert(2*index,left,mid,num);            insert(2*index+1,mid,right,num);        }        if(left>=mid&&right>mid)        {            insert(2*index+1,left,right,num);        }    }}//数海报数量,这里完全依赖于poster[]的记录来数海报数量,所以必须根据flag刷新被完全覆盖结点的海报编号. 判断条件依赖于: poster[] 中有编号，混合海报，没有覆盖海报，一共三个情况。void count(int index){    if(flag[index]!=NO_FLAG)    {        clear(index);    }    if(poster[index]!=NO_POSTER)    {        if(poster[index]!=MIX_POSTER)        {            if(ref[poster[index]]==0)            {                ref[poster[index]]=1;                ++count_poster;            }        }        else        {            count(2*index);            count(2*index+1);        }    }}int main(){    node_num=0;    count_poster=0;    memset(ref,0,sizeof(ref));        int num;//海报数量    int left,right;//海报覆盖范围    cin>>left>>right>>num;//输入墙的范围    construct(left,right);//构造线段树    for(int cnt=1;cnt<=num;++cnt)    {        cin>>left>>right;        insert(1,left,right,cnt);    }    count(1);    cout<<count_poster<<endl;    }