＜P5464 缩小社交圈＞
题目描述
社交圈子里有 n 个人，每个人都有一个 SAN 值范围 [li,ri]。当两个人的 SAN 值交集不为空时，这两个人有 PY 关系。
现在希望从社交圈子里面挑选出一些人组成一个集合 S，如果将所有集合内的人中有 PY 关系的那一对人都连上边，则 S 刚好成为一个树（森林不行哦）。
请问，有多少种可以选择的方案？由于答案可能很大，请对 109+7 取模。
输入格式
第一行一个整数 n。
接下来 n 行，每行 2 个整数，表示这个人的 SAN 值区间。
输出格式
一行一个整数，表示答案。
输入输出样例
输入 #1复制
3 1 5 2 7 4 8
输出 #1复制
6
说明/提示
对于20%的数据，满足 n≤18 。
对于40%的数据，满足 n≤50
对于60%的数据，满足 n≤200
对于100%的数据，满足 n≤2000,1≤li<ri≤4000
代码实现：
#include<bits/stdc++.h> using namespace std; #define int long long const int mod=1e9+7; inline void rd(int &x) { x=0;int p=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')p=-p;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch-'0'),ch=getchar(); x*=p; } int n,dp[2005][2005],pre[2005][2005],sl[4005],sr[4005]; struct nd {int l,r;}p[2005]; bool cmp(const nd&a,const nd&b) { if(a.l!=b.l)return a.l<b.l; return a.r<b.r; } int mn(int x,int y) {return x<y?x:y;} int mx(int x,int y) {return x>y?x:y;} void add(int &x,int y) { x+=y; if(x>=mod)x-=mod; if(x<0)x+=mod; } signed main() { rd(n); for(int i=1;i<=n;++i) {rd(p[i].l);rd(p[i].r);} sort(p+1,p+n+1,cmp); for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if(p[i].r>=p[j].l)dp[i][j]=1; p[n+1].l=99999999; sl[0]=0,sr[0]=0; for(int i=1;i<=4000;++i) { sl[i]=sl[i-1]; sr[i]=sr[i-1]; while(p[sl[i]].l<i)sl[i]++; while(p[sr[i]+1].l<=i)sr[i]++; } for(int i=1;i<=n;++i) { for(int j=i+1;j<=n;++j) { if(!dp[i][j])continue; add(pre[i][j],pre[i][j-1]); add(dp[i][j],pre[i][j]); if(p[i].r==p[j].r)continue; int x=mn(p[i].r,p[j].r); int y=mx(p[i].r,p[j].r); int L=sl[x+1]; int R=sr[y]; if(L>R)continue; if(p[i].r>p[j].r)add(pre[i][L],dp[i][j]),add(pre[i][R+1],-dp[i][j]); else add(pre[j][L],dp[i][j]),add(pre[j][R+1],-dp[i][j]); } } int ans=n; for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) add(ans,dp[i][j]); printf("%lld\n",ans); return 0; }