题解

题意重述：给定 $N$ 个区间 $[A_i,B_i]$（$A_i$ 表示到港时刻，$B_i$ 表示离港时刻），要将每个区间分配到两个栈之一，使得每个栈内按时间顺序“到港入栈、离港出栈”均合法，即同一栈内的区间必须满足括号序性质（不能出现“交叉”）。求可行分配方案数模 $10^9+7$。

关键结论：将区间视为 $1\ldots 2N$ 上的弦，两个区间“相交”（$A_i<A_j<B_i<B_j$ 或 $A_j<A_i<B_j<B_i$）当且仅当它们不能放在同一栈中。于是得到冲突图 $G$：每个区间为点，若两区间相交加一条边，要求将点染成两色使每条边两端颜色不同，即判定 $G$ 是否为二分图。若可二分，则每个连通分量可整体翻色而不影响可行性，答案是 $2^{\#\text{连通分量}}\bmod (10^9+7)$；若出现奇环则无解、答案为 $0$。

如何在线性时间内构造冲突边：按时刻 $1\ldots 2N$ 扫描维护“当前未闭合的区间”的栈 $S$。

• 扫描到某个到港时刻 $A_x$（即开端）时，将编号 $x$ 入栈。
• 扫描到某个离港时刻 $B_x$（即闭端）时，从栈顶不断弹出区间 $y$，直到弹出 $x$ 的开端为止。在此过程中，所有被弹出的 $y$ 都满足 $A_x<A_y<B_x<B_y$，与 $x$ 形成一条“相交边”，需要在 $G$ 中连边并强制 $x,y$ 分属不同颜色。

实现细节与优化：

• 使用并查集带按位奇偶（“带权并查集”）维护二分约束：对每条相交边 $x\sim y$ 合并集合，并记录 $\text{color}(x)\oplus \text{color}(y)=1$。若合并时发现矛盾（同集合且奇偶相同），则直接输出 $0$。
• 直接对每个 $x$ 与所有“跨过 $B_x$ 的未闭合区间”逐个连边会退化为 $O(N^2)$。代码利用链表式拼接 head/tail/pre/link 把同一段连续被弹出的区间“连成串”，并在并查集合并时只做必要的合并，整体线性（或线性对数）复杂度。
• 最终连通分量数从 $N$ 开始，每合并一次跨集合的约束就将分量数减 $1$。若无矛盾，答案为 $2^{\text{分量数}}\bmod (10^9+7)$。

复杂度：整趟扫描与按段合并均摊 $O(N)$，并查集操作近似 $O(\alpha(N))$；内存 $O(N)$。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

const int MAXN = 4000005;

int n, ans, ANS = 1, top;
int S[MAXN];
int fa[MAXN];
int bel[MAXN];
int match[MAXN];
int pre[MAXN];
int head[MAXN];
int tail[MAXN];

bool par[MAXN];

bool getval(int u) {
    return u == fa[u] ? 0 : getval(fa[u]) ^ par[u];
}

int getroot(int u) {
    if (u == fa[u])
        return u;

    int rt = getroot(fa[u]);
    par[u] ^= par[fa[u]];
    return fa[u] = rt;
}

void merge(int u, int v) {
    int ru = getroot(u), rv = getroot(v);
    par[ru] = getval(u) ^ getval(v) ^ 1;
    fa[ru] = rv;
}

void link(int u, int v) {
    pre[head[v]] = tail[u];
    head[v] = head[u];
}

void pop(int u) {
    if (head[u] == tail[u])
        head[u] = tail[u] = 0;
    else
        tail[u] = pre[tail[u]];
}

int main() {
    scanf("%d", &n);
    ans = n;

    for (int a, b, i = 1; i <= n; i++) {
        scanf("%d%d", &a, &b);

        if (a > b) {
            puts("0");
            return 0;
        }

        bel[a] = bel[b] = i;
        match[b] = a;
    }

    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        head[i] = tail[i] = i;
    }

    for (int i = 1; i <= 2 * n; i++) {
        if (!match[i])
            S[++top] = bel[i];
        else {
            int st = 0;

            while (1) {
                int cur = S[top--];

                if (tail[cur] == bel[i]) {
                    pop(cur);

                    if (tail[cur])
                        top++;

                    break;
                }

                if (getroot(cur) == getroot(bel[i])) {
                    if (getval(cur) == getval(bel[i])) {
                        puts("0");
                        return 0;
                    }
                } else {
                    ans--;
                    merge(cur, bel[i]);
                }

                if (!st)
                    st = cur;
                else
                    link(cur, st);
            }

            if (st)
                S[++top] = st;
        }
    }

    while (ans--)
        (ANS <<= 1) %= 1000000007;

    printf("%d\n", ANS);
    return 0;
}