Input
There are several test cases. For each test case, the first line contains two integers N, M (0<N, M<=100000) as described above. In each following N lines, there are two integers indicate two endpoints of the i-th interval. Then come M lines and each line contains two integers indicating the endpoints of the i-th query.
You can assume the left-endpoint is strictly less than the right-endpoint in each given interval and query and all these endpoints are between 0 and 1,000,000,000.OutputFor each query, you need to output the maximum number of the disjoint intervals in the asked interval in one line.
Sample Input
3 2 1 2 2 3 1 3 1 2 1 3
Sample Output
1 2
1 #include<bits/stdc++.h> 2 using namespace std; 3 inline int max(int x,int y) {return x>y?x:y;} 4 inline int min(int x,int y) {return x<y?x:y;} 5 inline int read() 6 { 7 int x=0,f=1; 8 char c=getchar(); 9 while(c<‘0‘ || c>‘9‘) {if(c==‘-‘) f=-1;c=getchar();} 10 while(c>=‘0‘ && c<=‘9‘) x=x*10+c-‘0‘,c=getchar(); 11 return x*f; 12 } 13 const int N=100005; 14 int f[4*N][22],n,m,num[4*N],len; 15 struct node 16 { 17 int l,r; 18 }q[N],a[N]; 19 inline bool cmp(node x,node y) {return x.r<y.r;} 20 21 int main() 22 { 23 while(scanf("%d%d",&n,&m)!=EOF) 24 { 25 memset(f,0x7f,sizeof(f)); 26 len=0; 27 int maxr=0; 28 for(int i=1;i<=n;i++) a[i].l=read(),a[i].r=read(),num[++len]=a[i].l,num[++len]=a[i].r; 29 for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),num[++len]=q[i].l,num[++len]=q[i].r; 30 sort(num+1,num+len+1); 31 len=unique(num+1,num+len+1)-num-1; 32 maxr=num[len]; 33 for(int i=1;i<=n;i++) a[i].l=lower_bound(num+1,num+len+1,a[i].l)-num; 34 for(int i=1;i<=n;i++) a[i].r=lower_bound(num+1,num+len+1,a[i].r)-num; 35 for(int i=1;i<=m;i++) q[i].l=lower_bound(num+1,num+len+1,q[i].l)-num; 36 for(int i=1;i<=m;i++) q[i].r=lower_bound(num+1,num+len+1,q[i].r)-num; 37 sort(a+1,a+n+1,cmp); 38 int posl=0; 39 for(int i=1;i<=n;i++) 40 { 41 for(int j=posl+1;j<=a[i].l;j++) f[j][0]=min(f[j][0],a[i].r); 42 posl=max(posl,a[i].l); 43 } 44 for(int j=1;(1<<j)<=n;j++) 45 for(int i=1;i<=maxr;i++) 46 { 47 if(f[i][j-1]>maxr) break; 48 f[i][j]=f[f[i][j-1]][j-1]; 49 } 50 for(int i=1;i<=m;i++) 51 { 52 int pos=q[i].l,ans=0; 53 for(int j=20;j>=0;j--) 54 if(f[pos][j]<=q[i].r) 55 { 56 pos=f[pos][j]; 57 ans+=(1<<j); 58 } 59 printf("%d\n",ans); 60 } 61 } 62 return 0; 63 }
原文：https://www.cnblogs.com/qshjydzh/p/12340347.html