题目描述

　　数轴上有\(n\)个人，每个人的位置是\(x_i\)，速度是\(v_i\)。

　　最开始有一些人感染了传染病。

　　如果某一时刻一个正常人和一个被感染的人处于同一位置，那么这个正常人也会被感染。

　　问所有\(2^n\)中初始感染情况中，有多少种情况在足够长时间后，所有人都被感染了。

　　\(n\leq 200000,v_i>0,x_i,v_i\)互不相同。

题解

　　显然在足够久之后，人们的位置顺序就是速度顺序。

　　考虑只有第\(i\)个人感染传染病会对最终情况有什么影响。

　　找到会被他传染的速度最快的人和速度最慢的人，那么在最后的序列中，这两个人之间的所有人都是能保证被传染的。

　　所以每个人传染的范围是一个区间。

　　如果初始感染的人的区间的并覆盖了所有人，那么这就是一组合法的方案。

　　直接DP即可。

　　时间复杂度：\(O(n\log n)\)

题解

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

#include<cmath>

#include<functional>

#include<vector>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

void sort(int &a,int &b)

{

	if(a>b)

		swap(a,b);

}

void open(const char *s)

{

#ifndef ONLINE_JUDGE

	char str[100];

	sprintf(str,"%s.in",s);

	freopen(str,"r",stdin);

	sprintf(str,"%s.out",s);

	freopen(str,"w",stdout);

#endif

}

int rd()

{

	int s=0,c;

	while((c=getchar())<'0'||c>'9');

	do

	{

		s=s*10+c-'0';

	}

	while((c=getchar())>='0'&&c<='9');

	return s;

}

void put(int x)

{

	if(!x)

	{

		putchar('0');

		return;

	}

	static int c[20];

	int t=0;

	while(x)

	{

		c[++t]=x%10;

		x/=10;

	}

	while(t)

		putchar(c[t--]+'0');

}

int upmin(int &a,int b)

{

	if(b<a)

	{

		a=b;

		return 1;

	}

	return 0;

}

int upmax(int &a,int b)

{

	if(b>a)

	{

		a=b;

		return 1;

	}

	return 0;

}

const ll p=1000000007;

int n;

int d[200010];

pii a[200010];

int pre[200010];

int suf[200010];

vector<int> c[200010];

ll f[200010];

ll s[200010];

int main()

{

	open("a");

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		scanf("%d%d",&a[i].first,&a[i].second);

		d[i]=a[i].second;

	}

	sort(a+1,a+n+1);

	sort(d+1,d+n+1);

	for(int i=1;i<=n;i++)

		a[i].second=lower_bound(d+1,d+n+1,a[i].second)-d;

	for(int i=1;i<=n;i++)

		pre[i]=max(pre[i-1],a[i].second);

	suf[n+1]=0x7fffffff;

	for(int i=n;i>=1;i--)

		suf[i]=min(suf[i+1],a[i].second);

	for(int i=1;i<=n;i++)

		c[pre[i]].push_back(suf[i]);

	f[0]=1;

	s[0]=1;

	for(int i=1;i<=n;i++)

	{

		for(auto v:c[i])

		{

			s[i]=(s[i-1]+f[i])%p;

			f[i]=(f[i]+s[i]-(v>=2?s[v-2]:0))%p;

		}

		s[i]=(s[i-1]+f[i])%p;

	}

	ll ans=f[n];

	ans=(ans+p)%p;

	printf("%lld\n",ans);

	return 0;

}