posters

叁歲伎倆 2022-08-11 16:55 7阅读 0赞

描述

The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:   
• Every candidate can place exactly one poster on the wall.   
• All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).   
• The wall is divided into segments and the width of each segment is one byte.   
• Each poster must completely cover a contiguous number of wall segments.  
  
They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.   
Your task is to find the number of visible posters when all the posters are placed given the information about posters' size, their place and order of placement on the electoral wall.  ![20101015164625_92163.jpg][]

输入

The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers li and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= li <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered li, li+1 ,... , ri.

输出

For each input data set print the number of visible posters after all the posters are placed.   
  
The picture below illustrates the case of the sample input.   
http://acm.pku.edu.cn/JudgeOnline/images/2528\_1.jpg

样例输入

1
    5
    1 4
    2 6
    8 10
    3 4
    7 10

样例输出

/*为大家方便明白，注释比较多。该题可学会线段树简单用法，学会数据的离散化，还是一个不错的题。*/
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define maxnum 20005
    
    //定义海报结构体并声明相应空间，order 粘贴顺序pos表示两边位置
    struct post
    {
    	int order;
    	int pos;
    }poster[maxnum];
    
    //定义建树结构体并声明一个数组树，l 孩子边界 r孩子右边界vis 是否访问过
    struct{
    	int l, r;
    	bool vis;
    }node[20*maxnum];//粗略估计建树所需节点数。
    bool flag;
    
    //按海报位置排序用，用于离散化数据
    bool cmp1(post p1,post p2)
    {return p1.pos<p2.pos;}
    
    //按海报粘贴顺序排序用，用于查询树
    bool cmp2(post p1,post p2)
    {
    	if(p1.order>p2.order) return true;
    	else if(p1.order==p2.order) return p1.pos<p2.pos;
    	return false;
    }
    
    //用数组模拟二叉树建树u 为树的相应节点,注意：该方法适用只适用固定个数子树的树。
    void BuildTree(int left, int right, int u){       
    	node[u].l = left;
    	node[u].r = right;
    	node[u].vis = false;
    	if(left == right) return;
    	int mid = (left+right)>>1; //曾经周五讲课给大家说过，右移为除2操作
    	BuildTree(left, mid, u<<1); //左移为乘2操作
    	BuildTree(mid+1, right, (u<<1)+1);
    }
    
    //查询
    void query(int left, int right, int u){          
    	if(node[u].vis == true) return;
    	if(node[u].l == left && node[u].r == right){
    		node[u].vis = true;       //  修改。
    		flag = true;              //  对于新帖的海报，有区间可以让其露出来。
    		return;
    	}
    	if(right <= node[u<<1].r)
    		query(left, right, u<<1);
    	else if(left >= node[(u<<1)+1].l)
    		query(left, right, (u<<1)+1);
    	else{
    		query(left, node[u<<1].r, u<<1);
    		query(node[(u<<1)+1].l, right, (u<<1)+1);
    	}
    	//递归回来的时候，由于左右子结点性质的改变，必须对父结点信息进行相应的更改。
    	node[u].vis = node[u<<1].vis & node[(u<<1)+1].vis;
    }
    int main()
    {
    	int n,m,sum;
    	cin>>n;
    	while(n--)
    	{
    		sum=0;
    		cin>>m;
    		for (int i=0;i<m;i++)
    		{
    			cin>>poster[2*i].pos>>poster[2*i+1].pos;
    			poster[2*i].order=poster[2*i+1].order=i;
    		}
    /*	以下进行离散化，同样的上次周五讲课有跟大家讲到，这里再次详细举例：
     *	例如有一组数：10000 -100 100  100 500 2000  这些数的大小如果对我们来说并无太大意义，
     *	或者我们并不关心其大小，我们可以对其进行排序，然后根据每个数的位置进行相应的离散化
     *	如：排序后-100 100 100 500 2000 10000  离散化后：2 2 3 4 5。这样我们就把范围在-100到
     *	的数据离散化到范围为到的数据。用于该题可大大缩减建树所需规模。
     */
    		sort(poster,poster+2*m,cmp1);
    		int index=0,pre=-1;
    		for (int i=0;i<2*m;i++)
    		{
    			if(poster[i].pos !=pre && poster[i].pos !=pre+1)
    			{
    				pre=poster[i].pos;
    				++index;
    				poster[i].pos =++index;
    			}else if(poster[i].pos !=pre)
    			{
    				pre=poster[i].pos;
    				poster[i].pos =++index;
    			}
    			else poster[i].pos=index;
    		}
    		//按粘贴顺序排序，从最后向前查询是否可见。
    		sort(poster,poster+2*m,cmp2);
    		BuildTree(1,index, 1);
    		for (int i=0;i<2*m;i+=2)
    		{
    			flag=false;
    			query(poster[i].pos,poster[i+1].pos,1);
    			if(flag) sum++;
    		}
    		cout<<sum<<endl;
    	}
    }

[20101015164625_92163.jpg]: http://acm.nyist.net/JudgeOnline/admin/kind/attached/20101015164625_92163.jpg