Times
【问题描述 】
小 y 作为一名资深的 dotaer，对视野的控制有着深刻的研究。
每个单位在一段特定的时间内会出现在小 y 的视野内，除此之外的时间都在
小 y 看不到的地方。在小 y 看来，视野内的单位数量越多，他就越安全，因为这
意味着有可能藏在阴影中的单位就越少。
现在，小 y 已经知道了每个单位会在什么时候出现在视野内，他想知道，在
一段时间内，总共有多少个单位出现在他的视野内过。
【输入格式】
第一行有两个整数 n，m,表示一共有 n 个单位，而小 y 有 m 个问题。
接下来 n 行，每行两个数 a，b，表示这个单位 a 秒时出现在小 y 的视野内，
出现了 b 秒。
接下来 m 行，每行两个整数 x，y，表示从 x 秒开始，经过 y 秒，其中有多
少个单位出现过。
【输出格式】
m 行，即对于小 y 提出的每个问题的答案。
【输入样例 1】
3 2
2 5
0 10
5 8
0 6
8 2
【输出样例 1】
3
2
【输入样例 2】
1 2
0 10
9 1
10 1
【输出样例 2】
1
0
【数据范围】
30%的数据：
1<=n,m<=1000
100%的数据：
1<=n,m<=200000
1<=x,y,a,b<=maxlongint
/* * @Problem: Times * @Author: shenben * @Date: 2017-01-25 20:42:59 * @Analyse: (1)如果[a,b)和[c,d)不相交 则①要么b<=c;②要么d<=a (2)对于一个询问区间[c,d) 我们统计对n个已经给出的区间[a,b)出现这两种情况的次数 答案就是n-次数 */ #include<cstdio> #include<algorithm> using namespace std; #define O3 __attribute__((optimize("O3"))) #define IN inline O3 IN int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int N=2e5+5; struct node{ int pos,t,id; node(){} node(int pos,int t,int id):pos(pos),t(t),id(id){} bool operator <(const node &a)const{ return pos==a.pos?t<a.t:pos<a.pos; } }e[N<<2]; int n,m,cnt,ans[N],c[4]; O3 int main(){ freopen("times.in","r",stdin); freopen("times.out","w",stdout); n=read();m=read(); for(int i=0,x,y;i<n;i++){ x=read();y=read(); e[cnt++]=node(x,1,-1); e[cnt++]=node(x+y,2,-1); } for(int i=0,x,y;i<m;i++){ x=read();y=read(); e[cnt++]=node(x,3,i); e[cnt++]=node(x+y,0,i); } sort(e,e+cnt); for(int i=0;i<cnt;i++){ c[e[i].t]++; if(e[i].t==0) ans[e[i].id]+=c[1]; if(e[i].t==3) ans[e[i].id]-=c[2]; } for(int i=0;i<m;i++) printf("%d ",ans[i]); return 0; }