当前位置 : 主页 > 网页制作 > HTTP/TCP >

POJ2528Mayor's posters 线段树,离散化技巧

来源:互联网 收集:自由互联 发布时间:2021-06-16
题意:一个坐标轴从1~1e7,每次覆盖一个区间(li,ri),问最后可见区间有多少个(没有被其他区间挡住的) 线段树,按倒序考虑,贴上的地方记为1,每次看(li,ri)这个区间是否全是
  • 题意:一个坐标轴从1~1e7,每次覆盖一个区间(li,ri),问最后可见区间有多少个(没有被其他区间挡住的)
  • 线段树,按倒序考虑,贴上的地方记为1,每次看(li,ri)这个区间是否全是1,全是1就说明在它后面贴的把它给挡住了,否则该海报可见。
  • 然后就愉快的MLE了。。。。
  • 再看看数据范围,离散化如下,比如如果海报的左右端点如下
  • 那图中橙色的一块的大小其实对结果没有影响,可以把他们都缩为1

                             

  • 最后离散化结果如下图:

                    

  • 代码:
     1 #include <algorithm>
     2 #include <iostream>
     3 #include <cstdio>
     4 #define nmax 10010
     5 #define tn t[node]
     6 #define sl (node<<1)
     7 #define sr (1+(node<<1))
     8 
     9 using namespace std;
    10 int n;
    11 int inl[nmax],inr[nmax];
    12 struct tin{
    13     int pd,id,num,n2; //0 ->l  1->r
    14     bool operator < (const tin x) const { return x.num>num; }
    15 }in[nmax*2];
    16 struct segt { int l,r,v; }t[nmax*15];
    17 
    18 void build(int node,int l,int r){
    19     tn.l=l;
    20     tn.r=r;
    21     tn.v=0;
    22     if(l==r) return;
    23     int mid=(l+r)>>1;
    24     build(sl,l,mid);
    25     build(sr,mid+1,r);
    26 }
    27 
    28 int upd(int l,int r,int node,int tv){
    29     int ta=(tv||tn.v);
    30     if(tn.l>=l&&tn.r<=r) tn.v=1;
    31     else{
    32         int mid=(tn.l+tn.r)>>1;
    33         int tl=1,tr=1;
    34         if(l<=mid) tl=upd(l,r,sl,tv||tn.v);
    35         if(r>mid) tr=upd(l,r,sr,tv||tn.v);
    36         ta=(tl&&tr)||tv;
    37         tn.v=tn.v||(t[sl].v&&t[sr].v);
    38     }
    39     return ta;
    40 }
    41 
    42 int main(){
    43     int cas;
    44     cin>>cas;
    45     while(cas--){
    46         cin>>n;
    47         for (int i=0; i<n; i++) {
    48             scanf("%d%d",&in[i].num,&in[i+n].num);
    49             in[i].pd=0;
    50             in[i+n].pd=1;
    51             in[i].id=in[i+n].id=i;
    52         }
    53         sort(in,in+2*n);
    54         //离散化
    55         int w=0;
    56         in[0].n2=(++w);
    57         for (int i=1; i<2*n; i++) {
    58             if(in[i].num==in[i-1].num ) {
    59                 in[i].n2=w;
    60                 continue;
    61             }
    62             in[i].n2=(++w);
    63             if( in[i].num!=in[i-1].num+1 ) in[i].n2=(++w);
    64         }
    65         //离散化over
    66         build(1,1,w);
    67         for (int i=0; i<2*n; i++) if(in[i].pd) inr[in[i].id]=in[i].n2; else inl[in[i].id]=in[i].n2;
    68         int ans=0;
    69         for (int i=n-1; i>=0; i--) if(upd(inl[i],inr[i],1,0)==0) ans++;
    70         printf("%d\n",ans);
    71     }
    72     return 0;
    73 }
网友评论