hiho1079 : 离散化(线段树+区间离散化)

#1079 : 离散化

时间限制: 10000ms

单点时限: 1000ms

内存限制: 256MB

描述

小Hi和小Ho在回国之后，重新过起了朝7晚5的学生生活，当然了，他们还是在一直学习着各种算法~

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

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

提示一：正确的认识信息量

提示二：小Hi大讲堂之线段树的节点意义

输入

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

每组测试数据的第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，表示总共有多少张海报能被看到。

样例输入

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

样例输出

5      

这道题我们首先想到的就是用线段树做  可是发现数据特别大

这时候就用到离散化了。

离散化  简而言之 就是把区间缩小  但是相对大小不变  这样就能用线段树维护了

当然 还有一个注意点就是 离散的区间是[l,mid],[mid,r]  而不是[l,mid],[mid+1,r].

至于为什么这样  可以用反证法~~如果[mid,mid+1]之间有一个海报怎么存贮？

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
struct node
{
  int flag;
  int l,r;
};
vector<int>v;
int res;
int N; 
bool use[100005*2+10];
node tree[40*100000];
int point_x[100005];
int point_y[100005];
int getid(int x)
{
  return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void build(int root,int l,int r)
{
  tree[root].flag=0;
  tree[root].l=l;
  tree[root].r=r;
  if(l+1==r) return ;
  int mid=(l+r)/2;
  build(root*2,l,mid);
  build(root*2+1,mid,r);
}
void update(int l,int r,int root,int x)
{
  
  if(tree[root].l==l&&tree[root].r==r)
  {
    tree[root].flag=x;
    return ;
  }
  if(tree[root].l+1>=tree[root].r) return;
  if(tree[root].flag)
  {
    tree[root*2+1].flag=tree[root*2].flag=tree[root].flag;
    tree[root].flag=0;
  }
  int mid=(tree[root].l+tree[root].r)/2;
  if(l>mid)
  update(l,r,root*2+1,x);
  else if(r<=mid)
  update(l,r,root*2,x);
  else
  {
    update(l,mid,root*2,x);
    update(mid,r,root*2+1,x);
  }
}
void query(int root)
{
  
  if(tree[root].flag&&!use[tree[root].flag])
  {
    res++;
    use[tree[root].flag]=true;
    return ;
  }
  if(tree[root].l+1>=tree[root].r) return ;
  if(!use[tree[root].flag]) 
  {
    query(root*2);
    query(root*2+1);
  }

}
int main()
{
  int n,l;
  memset(tree,0,sizeof(tree));
  v.clear(); 
  scanf("%d %d",&n,&l);
  for(int i=0;i<n;i++)
  {
    scanf("%d %d",&point_x[i],&point_y[i]);
    v.push_back(point_x[i]);
    v.push_back(point_y[i]);
  }
  sort(v.begin(),v.end());
  v.erase(unique(v.begin(),v.end()),v.end());
  N=v.size();
  build(1,1,N);
  for(int i=0;i<n;i++)
  {
    update(getid(point_x[i]),getid(point_y[i]),1,i+1);
  }
  res=0;
  memset(use,false,sizeof(use));
  query(1);
  printf("%d\n",res);
  return 0;
}