http://poj.org/problem?id=2528
题意是给你n个区间,后来的区间会覆盖前面的区间,问你最后有多少区间没有被完全覆盖
由于r的最大值是10000000,所以先将数据进行离散化处理,把所有所有区间的l,r排序,离散化后在从后往前去覆盖区间
如果该区间已经被覆盖,则返回false
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct Point { int x; int id; } point[4*20005]; struct Tree { int l,r; int vis; } tree[4*20005]; bool cmp1(Point a,Point b) { return a.x<b.x; } bool cmp2(Point a,Point b) { if(a.id==b.id) { return a.x<b.x; } return a.id>b.id; } void PushUp(int rt) { tree[rt].vis=tree[2*rt].vis&&tree[2*rt+1].vis; } void bulid(int rt,int L,int R) { tree[rt].vis=0; tree[rt].l=L; tree[rt].r=R; if(tree[rt].l==tree[rt].r) { return; } int mid=(L+R)/2; bulid(2*rt,L,mid); bulid(2*rt+1,mid+1,R); } bool query(int rt,int L,int R) { if(tree[rt].vis) { return false; } if(tree[rt].l==L&&tree[rt].r==R) { tree[rt].vis=1; return true; } bool isok=false; int mid=(tree[rt].l+tree[rt].r)/2; if(R<=mid) { isok = query(2*rt,L,R); } else if(L>=mid+1) { isok = query(2*rt+1,L,R); } else { isok = query(2*rt,L,mid)|query(2*rt+1,mid+1,R); } PushUp(rt); return isok; } int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); for (int i=0; i<2*n ; i+=2 ) { scanf("%d %d",&point[i].x,&point[i+1].x); point[i].id=point[i+1].id=i; } sort(point,point+2*n,cmp1); int pre=0,cnt=0; for (int i=0; i<2*n ; i++ ) { if(point[i].x==pre) { point[i].x=cnt; } else { pre=point[i].x; point[i].x=++cnt; } } int ans=0; bulid(1,1,cnt); sort(point,point+2*n,cmp2); for (int i=0; i<2*n ; i+=2 ) { if(query(1,point[i].x,point[i+1].x)) { ans++; } } printf("%d ",ans); } return 0; }