ZROI#972

ZROI#972

把所有连在一起的区间看作一个块,假设总共有 $x$ 个块,答案就是 $2^x$ .

用并查集可以维护,也可以不用并查集.

把区间以左端点为第一关键字,右端点为第二关键字,排序之后对于每个位置,从左往右扫,扫的时候判交即可.

对于无解:如果有一个点被三个线段同时覆盖,那么你无论如何都不能构造出一个合法的方案,因为只有两个集合,根据抽屉原理,无论如何都要有一个集合中包含两条线段,而它们必然相交.

$Code:$

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define int long long
#define pb push_back
#define db double
#define ull unsigned long long
#define lowbit(x) ( x & ( - x ) )
#define len(x) ( x.two - x.one + 1 )

using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;

template < class T >
    inline T read () {
        T x = 0 , f = 1 ; char ch = getchar () ;
        while ( ch < '0' || ch > '9' ) {
            if ( ch == '-' ) f = - 1 ;
            ch = getchar () ;
        }
       while ( ch >= '0' && ch <= '9' ) {
            x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
            ch = getchar () ;
       }
       return f * x ;
    }

const int N = 1e6 + 100 ;
const int mod = 998244353 ;
int n ; pii seg[N] ;

inline bool cmp (pii a , pii b) { return ( a.one < b.one ) || ( a.one == b.one && a.two < b.two ) ; }

inline int quick (int a , int p) { int res = 1 ; while ( p ) { if ( p & 1 ) res = ( res * a ) % mod ; a = ( a * a ) % mod ; p >>= 1 ; } return res ; }

signed main (int argc , char * argv[]) {
    n = rint () ; rep ( i , 1 , n ) seg[i].one = rint () , seg[i].two = rint () ;
    sort ( seg + 1 , seg + n + 1 , cmp ) ; int last = 0 , cnt = 0 ;
    rep ( i , 1 , n ) {
        if ( i > last ) last = i , ++ cnt ;
        while ( last < n && seg[i].two > seg[last+1].one ) {
            if ( last - i >= 1 && seg[last+1].one < seg[last].two )
                return puts ("0") , 0 ;
            ++ last ;
        }
    }
    printf ("%lld\n" , quick ( 2 , cnt ) % mod ) ;
    return 0 ;
}