LuoguP5464 缩小社交圈

背景:洛谷七月月赛T4

题目大意给定\(n\)个点,每个点的权值对应着一个区间\([l_i,r_i]\),两个点\(i,j\)有边当且仅当他们权值的并集不为空集,问有多少个点集\(S\)满足其连边后是一棵树

\(n <= 2*10^3,l_i<=r_i<=2*10^3\)

首先,这道题不能转换成一道图论问题去考虑,为什么?

因为这道题区间的性质非常特殊,是解题关键,如果转化成图,就没有了这个性质.

首先,如果不能转化成图论,此类区间的问题还是应该先进行排序.

我们按照\(r_i\)进行排序之后考虑\(DP\)

我们发现如果\(i\)与\(j\)的并集是空集,肯定\(i\)是无法接到\(j\)后面的

加入不为空集,就可能出现这种情况

这说明只记\(f_i\)表示前\(i\)个区间的合法数量是不对的

所以我们设\(f_{i,j}\)表示\(j\)接在\(i\)后面的方案数.

第一种情况:\(j\cap i!=j\),即\(x_i>x_j\)

此时,很明显有

\(f_{i,j} = \sum_{k = 0,y_k<x_i}^{j - 1}f_{j,k}\)

第二种情况:\(j\cap i==j\),即\(x_i<=x_j\)

很明显,此时我们在用上面的方程转移是不j合法的了

我们还应当保证,\(j,k\)无交

但是\(j,k\)无交就意味着\(f_{j,k}=0\)

之后我们发现,这种情况,\(f_{i,j}\)其实是可以从\(f_{i,k}\)转移过来的

即:

\(f_{i,j} = \sum_{k = 0,y_k<x_j}^{j - 1}f_{i,k}\)

发现上面两个方程都可以用前缀和或者树状数组优化

因为每次查询的符合答案的\(y_k\)是一个前缀

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cctype>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
using namespace std;
const int N = 4e3 + 3;
const int mod = 1e9 + 7; 
struct node{
    int li,ri;  
}a[N];
int f[N][N];
int n;
inline bool cmp(node x,node y){
    if(x.ri == y.ri)
    return x.li < y.li;
    return x.ri < y.ri;
}
inline void up(int &x,int y){
    x += y;
    if(x >= mod) x -= mod;  
}
struct BIT{
    int c[N];
    inline void add(int x,int v){
        for(;x <= 4000;x += x & -x) up(c[x],v);
    }
    inline int query(int x){
        int res = 0;
        for(;x;x -= x & -x) up(res,c[x]);
        return res; 
    }
}T[N];
//f[i][j]表示当前选了第i个,上一个选了第j个的方案总数 
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;++i) scanf("%d%d",&a[i].li,&a[i].ri);
    sort(a + 1,a + n + 1,cmp);
    for(int i = 1;i <= n;++i) f[i][0] = 1,T[i].add(1,1);
    for(int i = 1;i <= n;++i){
        for(int j = 0;j < i;++j){
            if(a[i].li > a[j].ri) continue;
            if(a[i].li <= a[j].li)
                up(f[i][j],T[i].query(a[j].li));    
            if(a[i].li > a[j].li)
                up(f[i][j],T[j].query(a[i].li));
            T[i].add(a[j].ri + 1,f[i][j]);
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;++i){
        for(int j = 0;j < i;++j) up(ans,f[i][j]);   
    }
    printf("%d\n",ans);
    return 0;   
}