YbtOj NOIP2020 模拟赛 B 组 Day8 T4 导出子图

文章目录

R e s u l t Result Result

---

H y p e r l i n k Hyperlink Hyperlink

https://www.ybtoj.com.cn/contest/62/problem/4

---

D e s c r i p t i o n Description Description

给定 n n n个区间， 定义有相交部分的区间在图上是相连的

求这张图有多少张子图是一棵树

数据范围： n ≤ 2 × 1 0 3 , r i ≤ 4 × 1 0 3 n\leq 2\times 10^3,r_i\leq 4\times 10^3 n≤2×103,ri​≤4×103

---

S o l u t i o n Solution Solution

问题就是求覆盖区间是相连的且同一段位置不会有三个区间覆盖的区间选择方案

也就是说每个区间实际只关心覆盖它的（规定左端点越小的越上面）以及与它同级的

按照左端点先排个序

设 f i , j f_{i,j} fi,j​表示处理到第 i i i个区间，当前覆盖的最右端点为 j j j的方案数
n x t [ i ] nxt[i] nxt[i]表示 i i i下一个左端点对应的编号-1

上图其实就对应了几种转移

第一种， f a x fa_x fax​类的，这种是自立为一棵新的树，即 f i , a [ i ] . r + = 1 f_{i,a[i].r}+=1 fi,a[i].r​+=1
第二种， y 1 , y 2 y_1,y_2 y1​,y2​类的，即两个区间并列，这些区间必须满足它们之间没有交（否则就不是树了），我们直接继承即可， f i , j + = f i − 1 , j f_{i,j}+=f_{i-1,j} fi,j​+=fi−1,j​
第三种， x , y 1 x,y_1 x,y1​类的，即 x x x完全包含 y 1 y_1 y1​，这种要满足 a [ i ] . r ≤ j a[i].r\leq j a[i].r≤j，即被包含在里面【因为左端点是升序的】，这样子的最优端点是没有变得，但是处理到的点到了 n x t [ a [ i ] . r ] nxt[a[i].r] nxt[a[i].r]，有转移 f n x t [ a [ i ] . r ] , j + = f i − 1 , j f_{nxt[a[i].r],j}+=f_{i-1,j} fnxt[a[i].r],j​+=fi−1,j​
第四种， x , z x,z x,z类的，即 z z z的左端点在 x x x以内，但它的右端点伸出去了，此时处理到的最右端点发生了改变，同时对应的处理到的点变成了 n x t [ j ] nxt[j] nxt[j]，即 f n x t [ j ] , a [ i ] . r + = f i − 1 , j f_{nxt[j],a[i].r}+=f_{i-1,j} fnxt[j],a[i].r​+=fi−1,j​

还有一种是根本没有相交的地方的，不管它就行了

最终答案即为 ∑ f n , i \sum f_{n,i} ∑fn,i​，时间复杂度： O ( n 2 ) O(n^2) O(n2)

---

C o d e Code Code

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define N 4010
#define mod 1000000007
using namespace std;int n,nxt[N];
struct node{int l,r;}a[N];
inline bool cmp(node x,node y){return x.l<y.l;}
LL f[N][N],res;
inline LL read()
{
	char c;LL d=1,f=0;
	while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;
	while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
	return d*f;
}
signed main()
{
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	n=read();
	for(register int i=1;i<=n;i++) a[i].l=read(),a[i].r=read();
	sort(a+1,a+1+n,cmp);
	a[n+1]=(node){4001,0};
	int j=0;
	for(register int i=1;i<=n+1;i++) while(j<a[i].l) nxt[j++]=i-1;
	for(register int i=1;i<=n;i++)
	{
		f[i][a[i].r]++;f[i][a[i].r]%=mod;
		for(register int j=1;j<=4000;j++)
		{
			(f[i][j]+=f[i-1][j])%=mod;
			if(a[i].l>j) continue;
			if(a[i].r<=j) (f[nxt[a[i].r]][j]+=f[i-1][j])%=mod;
			if(a[i].r>j) (f[nxt[j]][a[i].r]+=f[i-1][j])%=mod;
		}
	}
	for(register int i=1;i<=4000;i++) (res+=f[n][i])%=mod;
	printf("%lld",res);
}