[关闭]
@lunar 2016-07-06T14:25:40.000000Z 字数 2670 阅读 1321

HiHo一下 离散化 Week21

HiHo

描述

这天小Hi和小Ho所在的学校举办社团文化节，各大社团都在宣传栏上贴起了海报，但是贴来贴去，有些海报就会被其他社团的海报所遮挡住。看到这个场景，小Hi便产生了这样的一个疑问——最后到底能有几张海报还能被看见呢？

于是小Ho肩负起了解决这个问题的责任：因为宣传栏和海报的高度都是一样的，所以宣传栏可以被视作长度为L的一段区间，且有N张海报按照顺序依次贴在了宣传栏上，其中第i张海报贴住的范围可以用一段区间[a_i, b_i]表示，其中a_i, b_i均为属于[0, L]的整数，而一张海报能被看到当且仅当存在长度大于0的一部分没有被后来贴的海报所遮挡住。那么问题就来了：究竟有几张海报能被看到呢？

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第1行为两个整数N和L，分别表示总共贴上的海报数量和宣传栏的宽度。

每组测试数据的第2-N+1行，按照贴上去的先后顺序，每行描述一张海报，其中第i+1行为两个整数a_i, b_i，表示第i张海报所贴的区间为[a_i, b_i]。

对于100%的数据，满足N<=10^5，L <= 10^9，0<=a_i < b_i < =L。

输出

对于每组测试数据，输出一个整数Ans，表示总共有多少张海报能被看到。

样例

  1. 5 10
  2. 4 10
  3. 0 2
  4. 1 6
  5. 5 9
  6. 3 4

思路

这道题的基础算法是线段树，加上一点离散化的思想。
怎么应用线段树呢？我们这样来做，对于每个节点i,tree[i]存储当前结点表示区间的最上层海报，如果该区间内只有一张海报那么置为该海报的编号，若有多张海报，那么置为-1，若无海报置为0。在计算能被看到的海报个数时，对线段树遍历，对于每个节点，如果它的tree[i]不为0或-1的话说明该区间内最上层只有一张海报，检查其海报编号，若集合中没有那就加进去计数，如果tree[i]为-1，那就递归其子树，直到叶子节点。叶子结点表示区间长度为1，最上层最多就一张海报，所以如果tree[i]不为0的话那就将其海报编号加进去。建树的过程就是初始化，然后对每个海报信息依次进行线段树的更新，这里更新可以用到上一次提到的懒惰标号传递。
然而这样并不能解决所有问题，我们注意到,O(L)显然是不可接受的，但是仔细思考发现这个L似乎没什么用。我们需要的是各个海报之间的相互关系，也就是说若有两张海报那么{A=[1,100000],B=[2,1000005]}和{A=[1,3],B=[2,4]}是一样的。
这里就可以用到离散化的方法，我们将所有海报的端点信息排序去重，建立起原端点和新端点的双射关系。因为每个海报两个端点，所以最多有2*N个点，也就是说线段树的最多有 (4 * N)个节点，而，这样O（N）的复杂度就可以接受了。

代码

  1. #include<iostream> 
  2. #include<map>
  3. #include<algorithm> 
  4. #include<set>
  5. #include"math.h">
  6. using namespace std;
  7. #define MAX 100005
  8. #define lchild p<<1
  9. #define rchild p<<1|1
  10. int tree[2*MAX];
  11. int flag[2*MAX];
  12. int s[2*MAX];
  13. int a[MAX];
  14. int b[MAX];
  15. // Map the real coordinate and discrect coordinate
  16. std::map<int,int> distrete;
  18. //Set used to count the amount of post alive finally
  19. std::set<int> v;
  20. void buildTree(int l,int r,int p){
  21.     if(l+1==r){
  22.         tree[p] = 0;
  23.         flag[p] = -1;
  24.         return ;
  25.     }
  26.     tree[p] = 0;
  27.     flag[p] = -1;
  28.     int m = round((l+r)/2.0);
  29.     buildTree(l,m,lchild);
  30.     buildTree(m,r,rchild);
  31. }
  32. void update(int l, int r, int L, int R,int v, int p){
  33.     if(l<=L&&r>=R){
  34.         tree[p] = v;
  35.         flag[p] = 1;
  36.         return ;
  37.     }
  38.     if(flag[p] == 1){
  39.         tree[lchild] = tree[p];
  40.         tree[rchild] = tree[p];
  41.         flag[lchild] = 1;
  42.         flag[rchild] = 1;
  43.         flag[p] = -1;
  44.     }
  45.     int M = round((L+R)/2.0);
  46.     if(l<M) update(l,r,L,M,v,lchild);
  47.     if(r>M) update(l,r,M,R,v,rchild);
  48.     if((tree[lchild] == tree[rchild]) && (tree[lchild]!=-1)) tree[p] = tree[lchild];
  49.         else tree[p] = -1;
  50. }
  51. void stick(int n,int tn){
  52.     for(int i = 1;i<=n;i++){
  53.         int ta,tb;
  54.         std::map<int,int>::iterator it;
  55.         it = distrete.find(a[i]);
  56.         ta = it->second;
  57.         it = distrete.find(b[i]);
  58.         tb = it->second;
  59.         update(ta,tb,1,tn,i,1);     
  60.     }
  61. }
  63. void cnt(int l,int r, int p){
  64.     if((l+1==r) || (tree[p]!=-1)){
  65.         if(tree[p]!=0)v.insert(tree[p]);
  66.     }else{
  67.         int m = round((l+r));
  68.         cnt(l,m,lchild);
  69.         cnt(m,r,rchild);
  70.     }
  71. }
  72. int main(){
  73.     int n,l,ind=1,tn;
  74.     cin >> n >> l;
  76.     for(int i=1;i<=n;i++){
  77.         cin >> a[i] >>b[i];
  78.         s[ind++] = a[i];
  79.         s[ind++] = b[i];
  80.     }
  81.     tn = 2*n+1;
  82.     //Sort the coordinate
  83.     sort(s+1,s+tn); 
  84.     //Remove the duplication
  85.     tn = unique(s+1,s+tn) - (s+1);
  86.     for(int i = 1;i<=tn;i++){
  87.         distrete[s[i]] = i;
  88.     }
  89.     //Build segment tree    
  90.     buildTree(1,tn,1);
  91.     //Stick the post
  92.     stick(n,tn);        
  93.     cnt(1,tn,1);    
  94.     cout << v.size();
  95.     return 0;
  96. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注