poj 2528 线段树+离散化

题意：在墙上贴一堆海报（只看横坐标，可以抽象成一线段），新海报可以覆盖旧海报。求最后能看到多少张海报

sol：线段树成段更新。铺第i张海报的时候更新sg[i].x~sg[i].y这一段为i。

　　然而坐标范围有点大，还是加上离散化更靠谱些。

注意每组数据要清空数组，因为忘了清空WA了两发，太可惜了-_-||

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 using namespace std;
  6 struct
  7 {
  8     int l,r;
  9     int dat;
 10 }t[300010];
 11 struct
 12 {
 13     int x,y;
 14 }sg[300010];
 15 char ch;
 16 int md,num,ans,T,N,nnd;
 17 bool v[300010];
 18 int X[300010];
 19 
 20 //建树：
 21 void build(int l,int r,int o)
 22 {
 23     if (o>num) num=o;
 24     t[o].l=l;   t[o].r=r;
 25     if (l==r)
 26         t[o].dat=0;
 27     else
 28     {
 29         int mid=(l+r)/2;
 30         build(l,mid,2*o);
 31         build(mid+1,r,2*o+1);
 32         t[o].dat=0;
 33     }
 34 }
 35 
 36 //push_down：(向下更新一层)
 37 void push_down(int o)
 38 {
 39     if ((t[o].dat!=0)&&(t[o].dat!=md))
 40     {
 41         t[o<<1].dat=t[o].dat;
 42         t[o<<1|1].dat=t[o].dat;
 43         t[o].dat=0;
 44     }
 45 }
 46 
 47 //更新：cin>>ml>>mr>>md;    update(ml,mr,1);        ->令a[ml..mr]=md
 48 void update(int l,int r,int o)
 49 {
 50     if (o>num) return;
 51     int tl=t[o].l,tr=t[o].r;
 52     if ((tl==l)&&(tr==r))
 53     {
 54         t[o].dat=md;
 55         return;
 56     }
 57     else
 58     {
 59         int mid=(tl+tr)>>1;
 60         //if (tl==tr) return;
 61         push_down(o);
 62         if (r<=mid)
 63             update(l,r,o<<1);
 64         else if (l>mid)
 65             update(l,r,o<<1|1);
 66         else
 67         {
 68             update(l,mid,o<<1);
 69             update(mid+1,r,o<<1|1);
 70         }
 71     }
 72 }
 73 
 74 void sum(int o)
 75 {
 76     if (o>num) return;
 77     if (t[o].l!=t[o].r) push_down(o);
 78     if (t[o].dat!=0)
 79     {
 80         if (!v[t[o].dat])
 81         {
 82             v[t[o].dat]=true;
 83             ans++;
 84         }
 85         return;
 86     }
 87     sum(o<<1);
 88     sum(o<<1|1);
 89 }
 90 
 91 
 92 int Bin(int key,int n,int X[])
 93 {
 94     int l = 0 , r = n - 1;
 95     while (l <= r)
 96     {
 97         int m = (l + r) >> 1;
 98         if (X[m] == key) return m;
 99         if (X[m] < key) l = m + 1;
100         else r = m - 1;
101     }
102     return -1;
103 }
104 
105 int main()
106 {
107     cin>>T;
108     while(T--)
109     {
110         cin>>N;
111         nnd=0;
112         memset(t,0,sizeof(t));
113         memset(v,0,sizeof(v));
114         for(int i=1;i<=N;i++)
115         {
116             scanf("%d%d",&sg[i].x,&sg[i].y);
117             X[nnd++]=sg[i].x;
118             X[nnd++]=sg[i].y;
119         }
120         sort(X,X+nnd);
121         int m=1;
122         for(int i=1;i<nnd;i++)
123             if(X[i]!=X[i-1])    X[m++]=X[i];
124         sort(X,X+m);
125 
126         //for(int i=0;i<m;i++)
127         //    cout<<i<<"-"<<X[i]<<" ";
128         //cout<<endl;
129 
130         num=0;
131         build(1,m,1);
132         for(int i=1;i<=N;i++)
133         {
134             int tx=sg[i].x,ty=sg[i].y;
135             //cout<<tx<<" "<<ty<<"--";
136             tx=Bin(tx,m,X)+1;     ty=Bin(ty,m,X)+1;
137             //cout<<tx<<" "<<ty<<endl;
138             md=i;
139             update(tx,ty,1);
140         }
141         ans=0;
142         sum(1);
143 
144         cout<<ans<<endl;
145 
146     }
147     return 0;
148 }

View Code

现在再看去年这时候整理的线段树模板真是一坨屎。。。。