【BZOJ2422】Times

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

题解：这题的思路还是比较好的。

正着做比较难，考虑反着做。我们可以统计在那段时间内它没有看到过多少个单位，则要么b<x<y要么x<y<a，并且这两种情况不会重复计算，用树状数组统计一下就好了。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn=200010;

int n,m,nm,tot;

int x[maxn],y[maxn],l[maxn],r[maxn];

struct BIT

{

	int s[maxn<<2];

	inline void updata(int x)

	{

		for(int i=x;i<=nm;i+=i&-i)	s[i]++;

	}

	inline int query(int x)

	{

		int i,ret=0;

		for(i=x;i;i-=i&-i)	ret+=s[i];

		return ret;

	}

}s1,s2;

struct node

{

	int org,k;

	ll val;

}p[maxn<<2];

bool cmp(const node &a,const node &b)

{

	return a.val<b.val;

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	n=rd(),m=rd();

	int i;

	for(i=1;i<=n;i++) p[++tot].val=rd(),p[tot+1].val=p[tot].val+rd()-1,p[tot].org=p[tot+1].org=i,p[++tot].k=1;

	for(i=1;i<=m;i++) p[++tot].val=rd(),p[tot+1].val=p[tot].val+rd()-1,p[tot].org=p[tot+1].org=i,p[tot].k=2,p[++tot].k=3;

	sort(p+1,p+tot+1,cmp);

	p[0].val=-1;

	for(i=1;i<=tot;i++)

	{

		if(p[i].val>p[i-1].val)	nm++;

		switch(p[i].k)

		{

			case 0:x[p[i].org]=nm;	break;

			case 1:y[p[i].org]=nm;	break;

			case 2:l[p[i].org]=nm;	break;

			case 3:r[p[i].org]=nm;	break;

		}

	}

	for(i=1;i<=n;i++)	s1.updata(y[i]),s2.updata(x[i]);

	for(i=1;i<=m;i++)	printf("%d\n",n-(s1.query(l[i]-1)+s2.query(nm)-s2.query(r[i])));

	return 0;

}

巴特西

【BZOJ2422】Times 树状数组