题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4343
题目大意:给定N(N<=100000)个区间(左闭右开)和M(M<=100000)个询问[l, r],问所有满足[s,t)包含于于[l, r]的区间中最多能选出多少个,使得他们两两不相交。
解题思路:首先将坐标离散化,将区间排序后删掉可以覆盖其他区间的大区间。
这时若将剩余区间的左端点坐标排序,左端点坐标必然严格上升且对应的右端点坐标也是严格上升的。
此题的贪心思想较为普及,即按y的升序进行贪心固定区间询问的最大数量,不再赘述。
设g[1][x]为从坐标x开始向右遇到的第一个有效区间的右端点坐标,另g[i][x] = g[1][g[i-1][x]],若不存在则为正无穷。
则g[k][x]表示从坐标x开始,在经过不相交的k个区间后,第k个区间的右端点的坐标。
对g进行倍增,即设f[k][x] = g[2^k][x]。则对于一次询问(l,r),可利用f枚举答案各个二进制数位得到答案。
f[k][x] = f[k-1][f[k-1][x]],f[0][x] = g[1][x]。g只存在于思维过程中。
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; const int N=100050; int n,m,opt[20][N*2],x[N*2],cnt; struct node { int l,r; void read(){ scanf("%d%d",&l,&r); x[cnt++]=l; x[cnt++]=r; } void print(){ printf("%d %d\n",l,r); } bool operator <(const node tmp) const{ return l<tmp.l||(l==tmp.l&&r<tmp.r); } }no[N]; inline int getid(int val,bool f) { if(!f) return lower_bound(x,x+cnt,val)-x; return upper_bound(x,x+cnt,val)-x-1; } int calc(int l,int r) { if(l>r) return 0; if(l==cnt||r==-1) return 0; int ret=0; for(int i=19;i>=0;i--){ if(opt[i][l]<=r) { ret+=(1<<i); l=opt[i][l]; } } return ret; } int main() { // freopen("1.in","r",stdin); // freopen("2.out","w",stdout); while(scanf("%d%d",&n,&m)!=-1) { cnt=0; for(int i=0;i<n;i++){ no[i].read(); } sort(no,no+n); sort(x,x+cnt); cnt=unique(x,x+cnt)-x; for(int i=0;i<n;i++){ no[i].l=getid(no[i].l,0); no[i].r=getid(no[i].r,1); } x[cnt]=cnt; int mn=cnt,r=n; for(int i=cnt-1;i>=0;i--) { while(r>0&&no[r-1].l>=i){ r--; mn=min(mn,no[r].r); } opt[0][i]=mn; } for(int i=0;i<20;i++) opt[i][cnt]=cnt; for(int i=1;i<20;i++){ for(int j=0;j<cnt;j++){ opt[i][j]=opt[i-1][opt[i-1][j]]; } } while(m--) { int l,r; scanf("%d%d",&l,&r); l=getid(l,0); r=getid(r,1); printf("%d\n",calc(l,r)); } } return 0; }