题解 P3740 【[HAOI2014]贴海报】

le_星辰 · 2019-10-18 16:55:16 · 题解

这道题可以理解为给连续的一段区间染色，然后最后询问可以看见多少种颜色。题目并不复杂，我们可以这样考虑，最后放上去的海报一定不会被任何海报遮挡，于是可以先把海报存下来，然后在区间上逆序操作，需要的操作有：

• 1、询问一个区间是否被完全染色。

• 2、使一个区间全部染色。

  很明显这可以线段树来维护，用一个标记来表示区间是否被完全染色，传递信息可以用按位与“&”来支持， 然后spread等下传操作同线段树模板。

  但这题数据范围很大，需要离散化，第一次做这道题的时候只有70分，关键就在于离散化是分为两种类型的，第一种是连续性，第二种是离散型，所谓离散型的区间就是区间中的点集，例如[3,8]就代表了{3,4,5,6,7,8}，而另一种连续性则在数轴上是以一条线段来体现的，这道题就是连续型的离散化，于是就要进行一些操作以防相邻的区间将两个端点给误覆盖了，我的解决办法是离散三个关键点，除了左右端点外，再离散一个右端点+1的点，问题就解决了。

  上代码：

  #include <bits/stdc++.h>
  using namespace std;
  const int SIZE=1e4+10;
  struct node {
  int l,r;
  bool data,add;
  } t[4*SIZE];
  int n,Left[SIZE],Right[SIZE],m;
  int num[5*SIZE],ans,cnt,tot;
  void build(int p,int l,int r) {
  t[p].l=l,t[p].r=r;
  if(l==r) {
      t[p].data=false;
      return;
  }
  int mid=(l+r)/2;
  build(p*2,l,mid);
  build(p*2+1,mid+1,r);
  }
  void spread(int p) {
  if(t[p].add) {
      t[p*2].data=1;
      t[p*2+1].data=1;
      t[p*2].add=1;
      t[p*2+1].add=1;
      t[p].add=0;
  }
  }
  void change(int p,int l,int r) {
  if(l<=t[p].l&&r>=t[p].r) {
      t[p].data=1;
      t[p].add=1;
      return;
  }
  spread(p);
  int mid=(t[p].l+t[p].r)/2;
  if(l<=mid) change(p*2,l,r);
  if(r>mid) change(p*2+1,l,r);
  t[p].data=(t[p*2].data&t[p*2+1].data);
  }
  bool ask(int p,int l,int r) {
  if(l<=t[p].l&&r>=t[p].r) {
      return t[p].data;
  }
  spread(p);
  int mid=(t[p].l+t[p].r)/2;
  bool val=1;
  if(l<=mid) val&=ask(p*2,l,r);
  if(r>mid) val&=ask(p*2+1,l,r);
  return val;
  }
  int query(int x){
  return lower_bound(num+1,num+tot+1,x)-num;
  }
  int main() {
  scanf("%d%d",&n,&m);
  for(int i=1; i<=m; i++){
      scanf("%d%d",&Left[i],&Right[i]);
      num[++cnt]=Left[i];
      num[++cnt]=Right[i];
      num[++cnt]=Right[i]+1;//这就是离散右端点+1的点
  }
  sort(num+1,num+cnt+1);
  tot=unique(num+1,num+cnt+1)-(num+1);
  build(1,1,tot+10);
  for(int i=m; i>=1; i--) {
      int Le=query(Left[i]),Ri=query(Right[i]);
      if(!ask(1,Le,Ri)){
          ans++;
          change(1,Le,Ri);
      }
  }
  printf("%d",ans);
  return 0;
  }