Untitled

 avatar
unknown
plain_text
20 days ago
3.7 kB
3
Indexable
#include<iostream>
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 6e5 + 5, MOD = 998244353, INF = 1e9, block_size = sqrt(6e5);

int fac[N];
int inv[N];

void preprocess() {
    fac[0] = inv[0] = 1;
    fac[1] = inv[1] = 1;
    for (int i = 2; i < N; i++) {
        fac[i] = 1ll * i * fac[i - 1] % MOD;
        inv[i] = MOD - 1ll * MOD / i * inv[MOD % i] % MOD;
    }
    for (int i = 1; i < N; i++) {
        inv[i] = 1ll * inv[i - 1] * inv[i] % MOD;
    }

}

int cat(int n) {
    return 1ll * fac[2 * n] * inv[n] % MOD * inv[n + 1] % MOD;
}

int cat_rev(int n) {
    return 1ll * inv[2 * n] * fac[n] % MOD * fac[n + 1] % MOD;
}


int n;
set<int> bit[N];

void add(int idx, int val) {
    idx++;
    for (; idx <= 2 * n; idx += idx & -idx) {
        bit[idx].insert(val);
    }
}

int query(int idx, int r) {
    idx++;
    int ans = INF;
    for (; idx; idx -= idx & -idx) {
        auto it = bit[idx].upper_bound(r);
        if (it != bit[idx].end()) {
            ans = min(ans, *it);
        }
    }
    return ans;
}

int go[N];
int from_l_to_r[N];
int from_r_to_l[N];
int cnt[N];

void build(int b) {

    int l = b * block_size;
    int r = min(l + block_size - 1, 2 * n - 1);


    for (int i = r; i >= l; i--) {
        if (from_l_to_r[i] == i) {
            if (i == r) {
                cnt[i] = 1;
                go[i] = i + 1;
            } else {
                cnt[i] = 1 + cnt[go[i + 1]];
                go[i] = go[i + 1];
            }
        } else {
            if (from_l_to_r[i] >= r) {
                cnt[i] = 0;
                go[i] = from_l_to_r[i] + 1;
            } else {
                cnt[i] = cnt[from_l_to_r[i] + 1];
                go[i] = go[from_l_to_r[i] + 1];
            }
        }
    }
}

int cntSpaces(int l, int r) {
    int cnt_spaces = 0;
    while (l <= r) {
        if (go[l] <= r) {
            cnt_spaces += cnt[l];
            l = go[l];
        } else {
            if (from_l_to_r[l] == l) {
                cnt_spaces++;
                l++;
            } else {
                l = from_l_to_r[l] + 1;
            }
        }
    }
    return cnt_spaces;
}

void doWork() {
    cin >> n;
    for (int i = 1; i <= 2 * n; i++)bit[i].clear();


    for (int i = 0; i < 2 * n; i++) {
        from_l_to_r[i] = i;
        cnt[i] = 0;
    }
    go[2 * n] = 2 * n;
    cnt[2 * n] = 0;

    int rem = n;
    int ans = cat(rem);
    cout << ans << " ";
    vector<int> c(2 * n, 0);

    for (int i = 0; i <= (2 * n - 1) / block_size; i++)build(i);


    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        from_r_to_l[r] = l;
        from_l_to_r[l] = r;
        build(l / block_size);
        c[l] = cntSpaces(l + 1, r - 1) / 2;
        ans = 1ll * ans * cat(c[l]) % MOD;

        add(l, r);
        int prv = query(l - 1, r);

//        cout << prv << " " << rem << " " << c[l] << "\n";
        if (prv == INF) {
            ans = 1ll * ans * cat_rev(rem) % MOD;
            rem -= c[l] + 1;
            ans = 1ll * ans * cat(rem) % MOD;
        } else {
            prv = from_r_to_l[prv];
            ans = 1ll * ans * cat_rev(c[prv]) % MOD;
            c[prv] -= c[l] + 1;
//            cout << prv << " " << c[prv] << "\n";
            ans = 1ll * ans * cat(c[prv]) % MOD;
        }
//    cout<<rem<<"\n";
        cout << ans << " ";
    }
    cout << "\n";
}


int main() {
    preprocess();
    IO
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
//        cout << "Case #" << i << ": ";
        doWork();
    }
}

//.(..).
Leave a Comment