jzoj 6073.【GDOI2019模拟2019.3.20】河 dp+树状数组

Description

Input

Output

Sample Input

输入1：
3
2 5
6 1
3 7

输入2：
4
3 7
2 9
8 16
10 8

Sample Output
输出1：
6
说明：可行解有(2),(3),(1,2),(1,3),(2,3),(1,2,3)

输出2：
9

Data Constraint

分析：
对于一条直线，$y=k_ix+b_i$y=ki​x+bi​，对于其他直线$y=k_jx+b_j$y=kj​x+bj​，其中题目保证$b_i$bi​互不相同。
当$k_i&lt;k_j$ki​<kj​且$b_i&gt;b_j$bi​>bj​，那么这条直线可以被直接染色。
当$k_i≤k_j$ki​≤kj​且$b_i&lt;b_j$bi​<bj​，那么它只能被间接染色，而且被染过色的一条直线$y=k_lx+b_l$y=kl​x+bl​染色，其中$k_l&gt;k_j$kl​>kj​。
我们直接把所有直线按斜率排序，对于一条直线，他能染色的直线一定是一个区间。
这个区间的右边界是满足$k_i&lt;k_j$ki​<kj​且$b_i&gt;b_j$bi​>bj​，就是能直接染色中的斜率最大的直线。
左边界就是能直接染色中的斜率最小的直线。
然后就是区间覆盖问题。
我们对区间右边界进行排序，设$f[i]$f[i]表示使用了第$i$i个区间覆盖了$[1,r[i]]$[1,r[i]]的方案，因为$r$r是有序的，不会使得$r[i]$r[i]后面的位置被覆盖。于是就可以转移了。用树状数组优化。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define LL long long

const int maxn=5e5+7;
const LL mod=1e9+7;

using namespace std;

int n;
LL t[maxn],f[maxn];

struct rec{
	int k,b,num;
}a[maxn];

struct node{
	int l,r;
}q[maxn];

bool cmpk(rec a,rec b)
{
	if (a.k==b.k) return a.b<b.b;
	return a.k<b.k;
}

bool cmpb(rec a,rec b)
{
	return a.b<b.b;
}

bool cmp(node a,node b)
{
	if (a.r==b.r) return a.l<b.l;
	return a.r<b.r;
}

void updata(int x,int k)
{
	for (int i=x;i<=n+1;i+=i&(-i)) t[i]=(t[i]+(LL)k)%mod;
}

LL getsum(int x)
{
	LL sum=0;
	for (int i=x;i;i-=i&(-i)) sum=(sum+t[i])%mod;
	return sum;
}

LL calc(int l,int r)
{
	return (getsum(r)+mod-getsum(l-1))%mod;
}

int main()
{
	freopen("river.in","r",stdin);
	freopen("river.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&a[i].b,&a[i].k);	
	sort(a+1,a+n+1,cmpk);
	for (int i=1;i<=n;i++) a[i].num=i;
	sort(a+1,a+n+1,cmpb);	
	int maxx=0;
	for (int i=1;i<=n;i++)
	{
		maxx=max(maxx,a[i].num);
		q[a[i].num].r=maxx;
	}
	int minn=n+1;
	for (int i=n;i>0;i--)
	{
		minn=min(minn,a[i].num);
		q[a[i].num].l=minn;
	}
	sort(q+1,q+n+1,cmp);
	updata(1,1);
	for (int i=1;i<=n;i++)
	{
		f[i]=calc(q[i].l,q[i].r+1);
		updata(q[i].r+1,f[i]);
	}
	printf("%lld\n",calc(n+1,n+1));
}