1831E - Hyperregular Bracket Strings - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
#define ll long long
#define fu(i, a, b) for(ll i = a; i < b; i++)
#define fd(i, a, b) for(ll i = a - 1; i >= b; i--)
#define fastifier ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define x first
#define y second
#define nl '\n'
#define pl pair<ll, ll>
#define siz(x) (ll)x.size()
#define bit(i, k) (i & (1 << k))
#define cbit(i) __builtin_popcount(i)
#define fileInput freopen("inp.txt", "r", stdin);
#define fileOutput freopen("out.txt", "w", stdout);
#define uid(a, b) uniform_int_distribution<ll>(a, b)(rng) 
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template<class T> using ordset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template<class T> bool maxi(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}
 
template<class T> bool mini(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}
 
const ll inf = 1e15;
const ll mod = 998244353;
const ll def = 1e6+1;    

vector<ll> rg[def];
void dostuff(vector<pl> v){
    set<pl> s1, s2;

    fu(i, 0, siz(v)){
        s1.insert(v[i]);
        s2.insert({v[i].y, v[i].x});
    }

    while (siz(s1) > 0){
        pl p1 = *s1.rbegin();
        s1.erase(p1);

        swap(p1.x, p1.y);
        auto it = s2.lower_bound(p1);

        if (p1.x > (*s2.begin()).x){
            it--;
            pl p2 = *it;

            s2.erase(p1);
            swap(p1.x, p1.y);
            swap(p2.x, p2.y);

            if (p2.y < p1.x){
                rg[p1.x].push_back(p1.y);
                continue;
            }
            
            s1.erase(p2);
            swap(p2.x, p2.y);
            s2.erase(p2);
            swap(p2.x, p2.y);

            if (p2.x < p1.x){
                s1.insert({p2.x, p1.x - 1});
                s2.insert({p1.x - 1, p2.x});
            }

            s1.insert({p1.x, p2.y});
            s2.insert({p2.y, p1.x});

            if (p2.y < p1.y)
                rg[p2.y + 1].push_back(p1.y);
        }

        else{
            s2.erase(p1);
            rg[p1.y].push_back(p1.x);
        }
    }
}

void dostuff2(ll n){
    fu(i, 1, n + 1){
        if (siz(rg[i]) > 1){
            sort(rg[i].begin(), rg[i].end());
            vector<ll> v = rg[i];

            rg[i].clear();
            fu(j, 1, siz(v) + 1){
                if (j == siz(v) || v[j] != v[j - 1])
                    rg[i].push_back(v[j - 1]);
            }

            fu(j, 1, siz(rg[i])){
                if (rg[i][j - 1] < rg[i][j])
                    rg[rg[i][j - 1] + 1].push_back(rg[i][j]);
            }

            rg[i].clear();
            rg[i].push_back(v[0]);
        }
    }
}

ll res = 1;
ll fact[def], invf[def];

ll powmod(ll a, ll b){
    if (b == 0) return 1;
    if (b % 2 == 0){
        ll val = powmod(a, b / 2);
        return (val * val) % mod;
    }

    else
        return (powmod(a, b - 1) * a) % mod;
}

ll mmod(ll n){
    n %= mod;
    while (n < 0)   
        n += mod;

    return n;
}

ll catalan(ll n){
    ll res = fact[2 * n];
    res = mmod(res * invf[n + 1]);
    res = mmod(res * invf[n]);

    return res;
}

void initalize(){
    fact[0] = 1;
    fu(i, 1, def)
        fact[i] = (fact[i - 1] * i) % mod;

    invf[def - 1] = powmod(fact[def - 1], mod - 2);
    fd(i, def - 1, 0)
        invf[i] = mmod(invf[i + 1] * (i + 1));
}

void plswork(ll l, ll r){
    ll len = r - l + 1;
    fu(i, l, r + 1){    
        if (siz(rg[i]) > 0){
            if (i == l && rg[i][0] == r) continue;
            plswork(i, rg[i][0]);
            len -= rg[i][0] - i + 1;

            i = rg[i][0];
        }
    }

    res = mmod(res * catalan(len / 2));
}

void solve(){
    ll n, k;
    cin >> n >> k;

    res = 1;
    fu(i, 1, n + 1)
        rg[i].clear();

    vector<pl> v;
    fu(i, 0, k){
        ll l, r;
        cin >> l >> r;

        v.push_back({l, r});
    }

    v.push_back({1, n});
    dostuff(v);
    dostuff2(n);

    fu(i, 1, n + 1){
        fu(j, 0, siz(rg[i])){
            if ((rg[i][j] - i) % 2 == 0){
                cout << 0 << nl;
                return;
            }
        }
    }

    plswork(1, n);
    cout << res << nl;
}                   

int main(){
    fastifier; 
    ll t;
    cin >> t;

    initalize();
    while (t--)
    {
        solve();
    }
    
    return 0;
}