[LGR-059]缩小社交圈

题面描述

给定区间集合，交集不为空的互相连边，求所有生成树数量

题解

看见生成树就想到了矩阵树定理骗分，结果发现审错题了，就自闭了

智商什么时候可以练上去啊

根据题意，最后树的形态一定是有区间可以向只有相交关系的区间连边，且后者连的区间不能与其相交，向自己子区间连边时，子区间不能相交 并且从中我们可以看到一个区间能被正常计算，只有当其子区间已被计算过了，所以我们需要排序，按右端点为第一关键字，左端点为第二关键字排序即可

最后用前缀和优化即可

#include <cctype>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f =-1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x; 
}
const int N = 4e3+5, P = 1e9+7;
int n;
pair<int, int> p[N];
int pl[N], pr[N], f[N][N], g[N][N], h[N][N], ans;
int main()
{
    n = read();
    for(int i = 1; i <= n; ++i) 
    {
        int l = read(), r = read();
        p[i] = make_pair(r, l);
    } 
    sort(p+1, p+1+n);
    for(int i = 1; i <= n; ++i) pl[i] = p[i].second, pr[i] = p[i].first;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= i; ++j)
        {
            if(pl[j] < pl[i]&&pl[i] <= pr[j]) 
            {
                int k = lower_bound(pr+1, pr+1+n, pl[i])-pr-1;
                f[i][j] = (1+g[j][k])%P;
            }
            else if(pl[i] <= pl[j]&&pr[j] <= pr[i])
            {
                int k = lower_bound(pr+1, pr+1+n, pl[j])-pr-1;
                f[i][j] = (1+g[i][k])%P;
            }  
            ans = (ans+f[i][j])%P, g[i][j] = (g[i][j-1]+f[i][j])%P;
        }
    }
    printf("%d\n", ans);
    return 0;
}