题目描述

Description

小y作为一名资深的dotaer，对视野的控制有着深刻的研究。每个单位在一段特定的时间内会出现在小y的视野内，除此之外的时间都在小y看不到的地方。在小y看来，视野内的单位数量越多，他就越安全，因为这意味着有可能藏在阴影中的单位就越少。现在，小y已经知道了每个单位会在什么时候出现在视野内，他想知道，在一段时间内，
总共有多少个单位出现在他的视野内过。

Input

第一行有两个整数n，m,表示一共有n个单位，而小y有m个问题。
接下来n行，每行两个数a，b，表示这个单位a秒时出现在小y的视野内，出现了b秒。
接下来m行，每行两个整数x，y，表示从x秒开始，经过y秒，其中有多少个单位出现过。

Output

m行，即对于小y提出的每个问题的答案。

Sample Input

3 2
2 5
0 10
5 8
0 6
8 2

Sample Output

3
2

【数据范围】
1<=n,m<=200000
1<=x,y,a,b<=maxlongint

题目分析

先把所有的条件和询问离线下来，进行离散化
两条线段可能出现的相对位置是什么 相交或者不相交
我们发现 想要维护相交的情况比较困难 正所谓 正难则反 我们要维护不相交的情况 然后用总情况数减去它
不相交的情况有两种 右端点在左端点左面 左端点在右端点右面
那我们维护左端点的后缀和 右端点的前缀和即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
#define lson cnt<<1 
#define rson cnt<<1|1 
int n,m;
struct as
{
    int x,y;
}que[800100];   
long long q[800100];
int cnt;
int lsum[800100];
int rsum[800100];
int getid(int x)
{
    return lower_bound(q+1,q+cnt+1,x)-q;
}
int main()
{   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+m;i++)
    {
        scanf("%lld%lld",&que[i].x,&que[i].y);
        que[i].y=que[i].x+que[i].y-1;
        q[++cnt]=que[i].x;
        q[++cnt]=que[i].y;
    }
    sort(q+1,q+cnt+1);
    for(int i=1;i<=n+m;i++)
        que[i].x=getid(que[i].x),que[i].y=getid(que[i].y);
    for(int i=1;i<=n;i++)
        lsum[que[i].x]++,rsum[que[i].y]++;
    for(int i=cnt;i>=1;i--) lsum[i]+=lsum[i+1];
    for(int i=1;i<=cnt;i++) rsum[i]+=rsum[i-1];
    for(int i=n+1;i<=n+m;i++)
        printf("%d\n",n-rsum[que[i].x-1]-lsum[que[i].y+1]);
    return 0;
}