题目
描述
给出(n)条河流，每条河流是形式为(k_{i}x+b_{i})的一次函数且只有(x)轴正半轴的部分；
河流的污染部分和另外一条河流的干净部分交汇，干净的部分会被污染；
有若干个工厂要建在(b_{i})处，问有多少种方案使得所有的河流在无穷远处被污染；
答案对(1e9+7)取模
范围
$1 le N le 5 imes 10^5 , |k_{i}|,|b_{i}| le 10^9 $
保证(b_{i})互不相同；
题解
-
需要先找到可以被一条河流污染的所以河流
-
首先(b_{j}<b_{i}且k_{j}>k_{i}) 或者(b_{j}>b_{i}且k_{j}<k_{i}) 可以被直接污染;
-
对于每一条起源在(i)下方的(b_{j}<b_{i}且k_{j}>k_{i})河流(j) ，在河流(i)上方的部分会额外污染(b_{l}>b_{i}且k_{l}<k_{i})的河流
-
这样在下方我们就只需要考虑最大的(k_{j})即可；
-
同理在上方只需要考虑最小的(k_{j})；
-
所以污染一条河流意味着污染一个按(k)排序的区间；
-
剩下的就是线段覆盖，直接前缀和优化即可；
-
(不知道为什么不按左端点排序也可以(AC));
#include<bits/stdc++.h> #define mod 1000000007 using namespace std; const int N=500010; int n,m,sub[N],tot,rk[N],L[N],R[N],c[N]; vector<int>g[N]; char gc(){ static char*p1,*p2,s[1000000]; if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin); return(p1==p2)?EOF:*p1++; } int rd(){ int x=0,f=1;char c=gc(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc();} while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc(); return x*f; } struct P{int x,y,id;}p[N]; bool cmpy(const P&A,const P&B){return A.y==B.y?A.x<B.x:A.y<B.y;} bool cmpx(const P&A,const P&B){return A.x<B.x;} void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;} void add(int x,int y){for(++x;x<=n+1;x+=x&-x)inc(c[x],y);} int ask(int x){int re=0;for(++x;x;x-=x&-x)inc(re,c[x]);return re;} int main(){ freopen("river.in","r",stdin); freopen("river.out","w",stdout); n=rd(); for(int i=1;i<=n;++i)p[i].x=rd(),p[i].y=rd(),p[i].id=i; sort(p+1,p+n+1,cmpy); for(int i=1;i<=n;++i)rk[p[i].id]=i; sort(p+1,p+n+1,cmpx); R[0]=0;for(int i=1;i<=n;++i)R[i]=max(R[i-1],rk[p[i].id]); L[n+1]=n+1;for(int i=n;i;--i)L[i]=min(L[i+1],rk[p[i].id]); for(int i=1;i<=n;++i)g[R[i]].push_back(L[i]); add(0,1); for(int i=1;i<=n;++i) for(int j=0;j<(int)g[i].size();++j){ int l=g[i][j],tmp=ask(i); if(l>1)tmp=(tmp-ask(l-2)+mod)%mod; add(i,tmp); } int ans=(ask(n)-ask(n-1)+mod)%mod; cout<<ans<<endl; return 0; }