学步园

和poj2777涂颜色一样的思路。

线段树：1，一般是遇到(l==r)时，return；2，mid+1属于右子树。

#include<iostream><br /> #include<string><br /> #include<cstdio><br /> #include<algorithm><br /> using namespace std;<br /> #define maxn 100005<br /> bool vis[maxn];<br /> class node<br /> {<br /> public:<br /> int l,r;<br /> int step;<br /> };<br /> class point<br /> {<br /> public:<br /> int a,b;<br /> };<br /> point pro[maxn];<br /> int INDEX[maxn*2],cnt;<br /> node tree[maxn*4];<br /> int n;<br /> void build(int l,int r,int index)<br /> {<br /> tree[index].l =l;tree[index].r =r;<br /> tree[index].step =0;<br /> if(l==r) return;<br /> int mid=(l+r)>>1;<br /> build(l,mid,index*2);<br /> build(mid+1,r,index*2+1);<br /> }<br /> void insert(int l,int r,int step,int index)//插入一段区间<br /> {<br /> if(l==tree[index].l &&r==tree[index]. r)<br /> {<br /> tree[index].step =step;<br /> return ;<br /> }<br /> if(tree[index].step !=0&&tree[index].step!=step)<br /> {<br /> tree[index*2].step =tree[index].step ;//往后更新 这是核心<br /> tree[index*2+1].step =tree[index].step ;<br /> tree[index].step =0;<br /> }<br /> int mid=(tree[index].l +tree[index].r)>>1;<br /> if(l>mid) insert(l,r,step,index*2+1);<br /> else if(r<=mid) insert(l,r,step,index*2);<br /> else<br /> {<br /> insert(l,mid,step,index*2);<br /> insert(mid+1,r,step,index*2+1);<br /> }<br /> }<br /> void search(int index)//寻找还有多少颜色存在<br /> {<br /> if(tree[index].step !=0)<br /> {<br /> vis[tree[index].step ]=1;<br /> return ;<br /> }<br /> int mid=(tree[index].l +tree[index].r )>>1;<br /> search(index*2);<br /> search(index*2+1);<br /> }<br /> int getindex(int a)//二分查找对应的INDEX<br /> {<br /> int l=0,r=cnt-1;<br /> while(l<r)<br /> {<br /> int mid=(l+r)>>1;<br /> if(a<=INDEX[mid])<br /> r=mid;<br /> else l=mid+1;<br /> }<br /> return r;<br /> }<br /> int main()<br /> {<br /> int t,i,a,b;<br /> cin>>t;<br /> while(t--)<br /> {<br /> cin>>n;<br /> for(i=0;i<n;i++)<br /> {<br /> cin>>a>>b;<br /> pro[i].a=a;pro[i].b=b;<br /> INDEX[i*2]=a;INDEX[i*2+1]=b;<br /> }<br /> sort(INDEX,INDEX+2*n);<br /> cnt=0;<br /> for(i=1;i<n*2;i++)<br /> {<br /> if(INDEX[i]!=INDEX[i-1])<br /> INDEX[cnt++]=INDEX[i-1];<br /> }<br /> INDEX[cnt++]=INDEX[2*n-1];<br /> build(0,cnt-1,1);<br /> for(i=0;i<n;i++)<br /> {<br /> insert(getindex(pro[i].a),getindex(pro[i].b ),i+1,1);<br /> }<br /> memset(vis,0,sizeof(vis));<br /> search(1);<br /> int ans=0;<br /> for(i=1;i<=n;i++)<br /> if(vis[i])<br /> ans++;<br /> cout<<ans<<endl;<br /> }<br /> return 0;<br /> }