Untitled
#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