题解：AT_arc226_a [ARC226A] Meeting Division

C202301 · 2026-08-10 08:35:27 · 题解

观察一下发现两个人的计数问题本质上可以拆成两步：

• 判定是否为二分图。不是二分图必然无解。其中这个图是将有相交的两个区间连边。
• 对于一个连通块有两种方案，设连通块个数为 t，则方案数为 2^t。

对于第一步，区间图是弦图，判断是否存在奇环等价于是否存在点数为 3 的简单环，若存在此类环必然存在一个点其被三个区间覆盖，差分判定即可。

对于第二步，考虑每个连通块一定是一个区间，设其为 [l,r]，将区间对 r 排序，从小到大依次插入每个区间，每次插入区间等价于将一个后缀的连通块（按照 r 排序）合并成一个连通块，使用一个栈维护即可。最终栈中剩下的元素数量就是 t。

瓶颈在于排序。复杂度 O(n \log n)。代码如下：

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1e6;
using ll = long long;
constexpr ll mod = 998244353;
ll a[N + 5], n, p[N + 5];
struct Node {
    int s, t;
    bool operator < (const Node cpr) const {return t < cpr.t; }
}nd[N + 5];
ll qpow(ll x, ll y) {
    ll ans = 1; while(y) {if(y & 1) ans = ans * x % mod; x = x * x % mod; y >>= 1;}
    return ans;
}
vector<int> v;
int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> nd[i].s >> nd[i].t, --p[nd[i].t + 1], ++p[nd[i].s];
    sort(nd + 1, nd + n + 1);
    for(int i = 1; i <= n + n + 5; ++i) p[i] += p[i - 1];
    for(int i = 1; i <= n + n + 5; ++i) if(p[i] > 2) {cout << 0; return 0;}
    for(int i = 1; i <= n; ++i) {
        while(!v.empty() && v.back() > nd[i].s) v.pop_back();
        v.push_back(nd[i].t);
    }
    cout << qpow(2, v.size());
    return 0;
}