D - Interval query
Time Limit: 1.5 Sec
Memory Limit: 256 MB
Description
This is a very simple question. There are N intervals in number axis, and M queries just like “QUERY(a,b)” indicate asking the maximum number of the disjoint intervals between (a,b) .
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.
Output
For 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
HINT
题意
给你一些区间，现在有m个查询，求出每个查询的区间内的最大的不相交区间个数
题解：
二分，比赛的时候这样写，我艹了一直超时，赛后看了qscqesze多加了一个判断，加上去结果过了，太弱了
代码：
///
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <typeinfo>
#include <map>
typedef long long ll;
using namespace std;
#define inf 10000000
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//*************************************************************** struct ss
{
int x,y;
}a[],b[];
int lll;
int rrr;
bool cmp(ss a,ss b)
{
return a.y<b.y||(a.y==b.y&&a.x>b.x);
}
int n,l,r;
int main()
{
int m;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=; i<n; i++)
{
a[i].x=read();
a[i].y=read();
}
int tot=;
sort(a,a+n,cmp);
for(int i=;i<n;i++)
{
int flag=;
for(int j=i+;j<n;j++)
{
if(a[j].y>a[i].y)break;
if(a[j].x<a[i].x)continue;
flag=;
break;
}
if(!flag)b[tot++]=a[i];
}
n=tot;
for(int i=;i<=m;i++)
{
lll=read();
rrr=read();
int ans=;
l=;r=n-;
int aa=-;
while(l<=r)
{
int mid=(l+r)>>;
if(b[mid].y<=lll)
{
aa=mid;
l=mid+;
}
else r=mid-;
}
for(int i=aa+;i<n;i++)
{
if(b[i].y<=rrr)
{
if(b[i].x>=lll)ans++,lll=b[i].y;
}else break;
}
printf("%d\n",ans);
} }
return ;
}