学步园

题目链接：http://poj.org/problem?id=2528

题意：一段区间，前后用线段覆盖，问最后能在区间上看到的不同的线段数目．

区间染色问题，以不同的颜色向区间染色，问最后区间上的颜色总数．

区间操作，用线段树解决，注意lazy：

#include<stdio.h><br /> #include<string.h><br /> #include<stdlib.h><br /> #define M 40008<br /> #define L(x) (x<<1)<br /> #define R(x) ((x<<1)|1)<br /> #define MID(x,y) ((x+y)>>1)<br /> typedef struct{<br /> int l,r;<br /> }Poster;<br /> typedef struct{<br /> int l,r,c;//c<br /> }SegTree;<br /> SegTree tr[M*3];<br /> Poster p[M>>1];<br /> int x[M],xn,y[M];<br /> int ans,flag,n;<br /> int Cmp(const void *a,const void *b)<br /> {<br /> return *(int *)a-*(int *)b;<br /> }<br /> void Cal(int ix)<br /> {<br /> int mid=MID(tr[ix].l,tr[ix].r);<br /> if(tr[ix].l==tr[ix].r) return;<br /> tr[R(ix)]=tr[L(ix)]=tr[ix];<br /> tr[L(ix)].r=mid;tr[R(ix)].l=mid+1;<br /> tr[ix].c=1;<br /> }<br /> void Updata(int ix,Poster p)<br /> {<br /> int mid;<br /> if(tr[ix].c==2) return;<br /> if(!tr[ix].c) Cal(ix);<br /> if(p.l<=x[tr[ix].l]&&p.r>=x[tr[ix].r]){<br /> flag=0;tr[ix].c=2;return ;<br /> }<br /> mid=MID(tr[ix].l,tr[ix].r);<br /> if(p.r<=x[mid]) Updata(L(ix),p);<br /> else if(p.l>x[mid]) Updata(R(ix),p);<br /> else Updata(L(ix),p),Updata(R(ix),p);<br /> if(tr[L(ix)].c==2&&tr[R(ix)].c==2) tr[ix].c=2;<br /> }<br /> int main()<br /> {<br /> int t,i,j;<br /> scanf("%d",&t);<br /> while(t--){<br /> scanf("%d",&n);<br /> for(i=xn=0;i<n;i++){<br /> scanf("%d%d",&p[i].l,&p[i].r);<br /> y[xn++]=p[i].l;y[xn++]=p[i].r;<br /> }<br /> qsort(y,xn,sizeof(int),Cmp);<br /> for(i=1,j=0;i<xn;i++){<br /> if(y[i]==y[j]) continue;<br /> y[++j]=y[i];<br /> }xn=j+1;x[0]=y[0];<br /> for(i=j=1;i<xn;i++){<br /> if(y[i]-y[i-1]>1)<br /> x[j++]=MID(y[i],y[i-1]);<br /> x[j++]=y[i];<br /> }xn=j;<br /> tr[1].l=0;tr[1].r=xn-1;tr[1].c=0;<br /> for(ans=n,i=n-1;i>=0;i--){<br /> flag=1;<br /> Updata(1,p[i]);<br /> ans-=flag;<br /> }<br /> printf("%d/n",ans);<br /> }<br /> return 0;<br /> }<br />