题解 洛谷P2650

题意简化：求某个区间在一组区间中覆盖的数量

对于这个问题，我们很容易想到线段树，或者树状数组，但是maxlongint不能让我们这么做

30分思路:

对于m个区间，枚举n个区间判断与它是否重合

但是O（nm）显然会TLE

100分思路

把n个区间存入l,r树组里，从小到大排序.

对于每个询问x，y ,二分找l树组里第一个小于y的数的下标，假设为ans1，在r树组二分里找第一个小于x的数的下标，假设为ans2。ans1-ans2即为答案。

这个思路的原理其实是把区间两个端点抽象成数轴上的括号,

当找l树组里第一个小于y的数的下标时，其实是找y左边区间的数量，排除y右边区间的数量

在r树组里找第一个小于x的数的下标,其实是找左边与询问区间无交集的区间数量，可以求得x左边的无交集区间数量

两个答案相减，可以得到与x，y有交集的数量

.

.

STL的lower_bound函数可以帮忙偷懒

#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e5+1;
ll l[N],r[N];
bool cmp(ll a,ll b)
{
    return a<b;
}
int n,m;ll x,y;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&l[i],&r[i]);
        r[i]+=l[i]-1;
    }
    sort(l+1,l+1+n,cmp);
    sort(r+1,r+1+n,cmp);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&x,&y);
        y+=x;
        int l0=lower_bound(l+1,l+1+n,y)-l;
        int r0=lower_bound(r+1,r+1+n,x)-r;
        printf("%d\n",l0-r0);
        
    }
}

题解 洛谷P2650

原文：https://www.cnblogs.com/naruto-mzx/p/11282578.html