题目链接

本题的限制等价于把一堆区间分成两个集合,每个集合内的区间两两之间要么不相交,要么完全包含。

我们把限制建成一个无向图,每两个冲突的区间之间都连一条边。显然,如果建出来不是二分图,答案必定为$0$(一个奇环上无法黑白染色使得两两相邻不同色)。我们把孤立的点去掉(去掉每个点会使答案乘$2$),考虑左边的每个点$x$,记右边与它相邻的点为$S_x$,则$S_x$中的点肯定是同色的,且$x$的颜色由$S_x$的颜色唯一确定。所以我们只需要把每个$S_x$用并查集并起来,最后统计右边的连通块数就行了。

然而直接建图搞的复杂度是$O(n^2)$的,我们考虑优化。注意到二分图的两边都可以看成一个合法的括号序列,我们建出对应的树结构。设右边所有区间中包含$x$的左端点及右端点的最小区间分别为$y_1,y_2$,则$S_x$即为$y_1$到$y_2$路径上的所有点减去两个点的LCA。这个东西在树上用并查集随便搞搞就行了。

关于求初始的二分图,我的做法是直接广搜,搜完之后检查一下合法性。对区间左端点建一个线段树,线段树每个区间按右端点的顺序维护未访问的所有区间。这里可以做到$O(n\log n)$的复杂度,加上前面的求LCA,总复杂度为$O(n\log n)$。

#include <bits/stdc++.h>
#define MAXN 2000010
using namespace std;

const int P=1000000007;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res;
}

int n;
pair<int,int> p[MAXN];
int p1[MAXN],pt1[MAXN],pt2[MAXN];
int *s[MAXN*3],len[MAXN*3],cur[MAXN*3];
int c[MAXN],pre[MAXN][21],dep[MAXN],top[MAXN];
int f[MAXN];
queue<int> Q;

int getf(int x){
    if(f[x]==x) return x;
    return f[x]=getf(f[x]);
}

void build(int x,int l,int r){
    if(l==r){
        if(p1[l]){
            s[x]=new int[len[x]=1];
            s[x][0]=p1[l];
        }
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    int x0=0,x1=0,x2=0,l1=len[x<<1],l2=len[x<<1|1];
    s[x]=new int[len[x]=l1+l2];
    while(x1<l1 || x2<l2){
        if(x1==l1) s[x][x0++]=s[x<<1|1][x2++];
        else if(x2==l2) s[x][x0++]=s[x<<1][x1++];
        else if(p[s[x<<1][x1]].second>p[s[x<<1|1][x2]].second) s[x][x0++]=s[x<<1][x1++];
        else s[x][x0++]=s[x<<1|1][x2++];
    }
}

void extend(int x,int cl,int cr,int l,int r,int nc){
    if(l<=cl && cr<=r){
        while(cur[x]<len[x] && p[s[x][cur[x]]].second>r){
            int t=s[x][cur[x]++];
            if(c[t]==-1){
                c[t]=nc;
                Q.push(t);
            }
        }
        return;
    }
    int mid=(cl+cr)>>1;
    if(l<=mid) extend(x<<1,cl,mid,l,r,nc);
    if(r>mid) extend(x<<1|1,mid+1,cr,l,r,nc);
}

void bfs(int x){
    Q.push(x);
    c[x]=0;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        extend(1,1,n<<1,p[x].first,p[x].second,c[x]^1);
        extend(1,1,n<<1,1,p[x].first,c[x]^1);
    }
}

bool check(){
    static stack<int> S;
    for(int _i=1;_i<=n<<1;_i++){
        while(!S.empty() && p[S.top()].second<_i) S.pop();
        if(p1[_i] && !c[p1[_i]]){
            int i=p1[_i];
            if(!S.empty() && p[S.top()].second<p[i].second) return 0;
            if(!S.empty()) pre[i][0]=S.top();
            S.push(i);
            dep[i]=dep[pre[i][0]]+1;
            top[i]=pre[i][0]?top[pre[i][0]]:i;
        }
        if(!S.empty()) pt1[_i]=S.top();
    }
    while(!S.empty()) S.pop();
    for(int _i=1;_i<=n<<1;_i++){
        while(!S.empty() && p[S.top()].second<_i) S.pop();
        if(p1[_i] && c[p1[_i]]){
            int i=p1[_i];
            if(!S.empty() && p[S.top()].second<p[i].second) return 0;
            if(!S.empty()) pre[i][0]=S.top();
            S.push(i);
            dep[i]=dep[pre[i][0]]+1;
            top[i]=pre[i][0]?top[pre[i][0]]:i;
        }
        if(!S.empty()) pt2[_i]=S.top();
    }
    return 1;
}

void pre_gao(){
    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
            pre[j][i]=pre[pre[j][i-1]][i-1];
}

int getLCA(int x,int y){
    if(top[x]^top[y]) return 0;
    if(dep[x]>dep[y]) swap(x,y);
    int dd=dep[y]-dep[x];
    for(int i=0,l=1;l<=dd;i++,l<<=1)
        if(dd&l) y=pre[y][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
        if(pre[x][i]^pre[y][i])
            x=pre[x][i],y=pre[y][i];
    return pre[x][0];
}

void merge(int x,int y){
    int y0=y;
    y=getf(y);
    while((x=getf(x))^y){
        if(pre[x][0]^y0) f[x]=pre[x][0];
        x=pre[x][0];
    }
}

void query1(int x){
    printf("%d %d\n",pt2[p[x].first],pt2[p[x].second]);
}

void query2(int x){
    printf("%d %d\n",pt1[p[x].first],pt1[p[x].second]);
}

int gao(){
    int ans=1;
    static vector<pair<int,int> > qs;
    for(int i=1;i<=n;i++)
        if(!c[i]){
            int t1=pt2[p[i].first],t2=pt2[p[i].second];
            if((!t1 && !t2) || t1==t2) ans=ans*2%P;
            else if(!t1 || !t2){
                merge(t1+t2,0);
            }else{
                int lca=getLCA(t1,t2);
                if(t1==lca) merge(t2,t1);
                else if(t2==lca) merge(t1,t2);
                else{
                    merge(t1,lca); merge(t2,lca);
                    qs.push_back(make_pair(t1,t2));
                }
            }
        }
    for(auto i:qs)
        if(getf(i.first)^getf(i.second))
            f[f[i.first]]=f[i.second];
    for(int i=1;i<=n;i++)
        if(c[i] && getf(i)==i)
            ans=ans*2%P;
    return ans;
}

int main(){
#ifdef DEBUG
    freopen("356.in","r",stdin);
#endif
    n=read();
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=n;i++) p[i].first=read(),p[i].second=read();
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++) p1[p[i].first]=i;
    build(1,1,n<<1);
    memset(c,-1,sizeof c);
    for(int i=1;i<=n;i++)
        if(c[i]==-1) 
            bfs(i);
    if(!check()){
        puts("0");
        return 0;
    }
    pre_gao();
    printf("%d\n",gao());
}