https://codeforces.com/contest/2056/problem/E
题目大意
给出 $n \ (1 \le n \le 2 \times 10^5)$ 的范围和 $m \ (0 \le m \le 2 \times 10^5)$ 个区间，这些区间满足对于任意的 $i \neq j$：
- 它们不相同
- 它们要么不相交（$r_i < l_j$ 或者 $r_j < l_i$）要么一个包含另一个（$l_i \le l_j \le r_j \le r_i$ 或 $l_j \le l_i \le r_i \le r_j$）。
问有多少种方案可以增加尽可能多的 $1 \le l \le r \le n$ 的区间，使得所有区间仍旧满足上述的限制。答案模 $998244353$。
简要题解
观察：
- 所有给出的区间构成了一个森林
- 如果没有 $[1, n]$ 这个区间，则必然会增加 $[1, n]$ 区间，且增加前后的总方案数不会有变化。也就是说我们总可以通过这个方式把给出的图补全成一棵树。
- 考虑 $[1, n]$ 的空区间（没有其他已知区间），如果想让结果尽量多，则我们总会选取一个 $1$ 为左边界的区间（否则我们总会加上 $[1, 1]$ 使得最多区间数更多）
- 当第一段选了 $[1, x]$ 那么第二段一定是从 $x + 1$ 为左边界，直到把整段选完。以此类推，形象的说最后的区间是选“满”了的。
- 所有的选”满“了的方案其实都是最优的。
- 某个大区间里，如果某些段被选了，则可以把这些段当成 $1$ 长的段处理。
- 不同已经固定的区间的选取方案是独立的。
有了这些观察其实这个题就可以做了，这里需要证明其中的某些观察，以及数学化的定义“满”这件事。
1 是经典结论这里就不证明了。
2 很好证，因为如果某最优解没有 $[1, n]$ 则显然可以加入这个区间使得最优区间数量 $+1$。因为所有情况都要加入这个区间，因此题目条件中有没有加这个区间是没有区别的。
345 一起看。区间是 $[l, r]$ 还是 $[1, n]$ 在这个问题里是没有区别的。我们不妨只讨论 $[1, n]$。注意到其实这就是合法加法算式的个数！也就是说答案其实就是卡塔兰数 $C_{n - 1}$（计算数是 $n$ 个则括号有 $n - 1$ 个，因为每一组括号消耗掉一个计算数）。
67 一起看。对于树来说，对于某节点 $[l, r]$ 其有子树 $[x, y]$，则其选出的所有区间要么包含 $[x, y]$，要么与 $[x, y]$ 无关，要么被 $[x, y]$ 包含。显然被 $[x, y]$ 包含的区间与其他两者的选取无关，于是我们可以在子树中再处理。而因为包含或者无关的情况 $[x, y]$ 都被当做整体，因此相当于一个 $1$ 长的段，计算本节点时将其缩起来即可。
最后就是如何把这些区间转化成树。我们可以使用扫描线，注意这题因为包含可以有边界相等，因此排序需要比较注意。我们用栈维护当前还在开的区间，新加入的区间左边界，一定被包含在栈顶最好的区间，我们连边并将其入栈，遇到右边界则将栈顶出栈即可。注意我们总要让较短的区间在栈上部，因此排序时，同样左边界的，右边界靠右的长，要先进栈。同样右边界的，左边界靠右短，要先出栈。
复杂度
$T$：$O(n + m \log m)$
$S$：$O(n + m)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
template<long long Mo=998244353> struct ModInt {
static long long MO;
static void setMo(long long mo) { MO = mo; }
long long x;
ModInt(long long x=0) : x(x){ norm(); }
friend istream &operator>>(istream& in, ModInt &B) { in>>B.x; return in; }
friend ostream &operator<<(ostream& out, const ModInt &B) {
out<<B.x; return out; }
// ModInt operator=(int x_) { x=x_; norm(); return *this; }
void norm() { x = (x%MO + MO) % MO; }
long long get() { return x; }
ModInt operator-() const { return ModInt(MO - x); }
ModInt operator+=(const ModInt &B) { x+=B.x; if(x>=MO) x-=MO; return *this; }
ModInt operator-=(const ModInt &B) { x-=B.x; if(x<0) x+=MO; return *this; }
ModInt operator*=(const ModInt &B) { x=x*B.x%MO; return *this; }
ModInt operator+(const ModInt &B) const { ModInt ans=*this; return ans+=B; }
ModInt operator-(const ModInt &B) const { ModInt ans=*this; return ans-=B; }
ModInt operator*(const ModInt &B) const { ModInt ans=*this; return ans*=B; }
ModInt operator^(long long n) const {
ModInt a=*this; ModInt ans(1);
while(n) { if(n&1) ans*=a; a*=a; n>>=1; }
return ans;
}
ModInt inv() const { return (*this)^(MO-2); } // if MO is prime
ModInt operator/=(const ModInt &B) { (*this)*=B.inv(); return *this; }
ModInt operator/(const ModInt &B) const { ModInt ans=*this; return ans/=B; }
bool operator<(const ModInt &B) const { return x<B.x; }
bool operator==(const ModInt &B) const { return x==B.x; }
bool operator!=(const ModInt &B) const { return x!=B.x; }
};
template<long long Mo> long long ModInt<Mo>::MO = Mo;
typedef ModInt<998244353> Mint;
// typedef ModInt<1'000'000'007> Mint;
vector<Mint> inv, fa, ifa;
void init_mod(int n) {
inv.assign(n + 1, Mint(1));
fa.assign(n + 1, Mint(1));
ifa.assign(n + 1, Mint(1));
for(int i = 2; i <= n; i++) {
fa[i] = fa[i-1] * i;
inv[i] = Mint(Mint::MO - Mint::MO / i) * inv[Mint::MO % i];
ifa[i] = inv[i] * ifa[i-1];
}
}
inline Mint C(int n,int m) {
return (m<0 || n<m) ? Mint(0) : fa[n]*ifa[m]*ifa[n-m]; }
inline Mint A(int n,int m) { return fa[n]*ifa[n-m]; }
template<typename Func> struct YCombinatorResult {
Func func;
template<typename T>
explicit YCombinatorResult(T &&func) : func(std::forward<T>(func)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) {
return func(std::ref(*this), std::forward<Args>(args)...);
}
};
template<typename Func> decltype(auto) y_comb(Func &&fun) {
return YCombinatorResult<std::decay_t<Func>>(std::forward<Func>(fun));
}
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
/*
mx cnt
1 -> 1 -> 11
2 -> 3 -> 12 11 22 -> 1
3 -> 5 -> 13 11 23 22 33, 13 12 11 22 33 -> 2
4 -> 7 -> 14 13, 14 24, 14 12 34 -> 5
*/
const int M = 2e5 + 5;
vector<Mint> Cata;
void init_cata(int n) {
Cata.assign(n + 1, Mint(0));
for (int i = 0; i <= n; i++) {
Cata[i] = C(i * 2, i) * inv[i + 1];
}
}
void init() {
init_mod(M * 2);
init_cata(M);
}
struct Event {
int x, t, y, id;
bool operator<(const Event& B) const {
if (x != B.x) return x < B.x;
if (t != B.t) return t < B.t;
return y > B.y;
}
};
void solve() {
int n, m; cin >> n >> m;
vector<Event> evts;
vector<int> l(m), r(m);
int rt = -1;
for (int i = 0; i < m; i++) {
cin >> l[i] >> r[i];
evts.push_back({l[i], 0, r[i], i});
evts.push_back({r[i], 1, l[i], i});
if (l[i] == 1 && r[i] == n) {
rt = i;
}
}
if (rt == -1) {
l.push_back(1);
r.push_back(n);
evts.push_back({1, 0, n, m});
evts.push_back({n, 1, 1, m});
rt = m;
m++;
}
sort(evts.begin(), evts.end());
vector<vector<int>> g(m);
stack<int> st;
for (auto [x, t, y, id] : evts) {
if (!t) {
if (id != rt) {
g[st.top()].push_back(id);
}
st.push(id);
} else {
// assert(!st.empty());
st.pop();
}
}
// for (int i = 0; i < m; i++) {
// cerr << i << " : ";
// for (int j : g[i]) {
// cerr << j << ' ';
// }
// cerr << endl;
// }
Mint ans = y_comb([&](auto dfs, int u) -> Mint {
int tot = r[u] - l[u] + 1;
Mint ans = 1;
for (int v : g[u]) {
ans *= dfs(v);
tot -= r[v] - l[v] + 1;
}
tot += g[u].size() - 1;
// cerr << u << ' ' << l[u] << ' ' << r[u] << ' ' << ans << ' ' << tot << endl;
ans *= Cata[tot];
return ans;
})(rt);
cout << ans << '\n';
}
int main() {
init();
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] A. Tricky Template - Educational Codeforces Round 161 (Rated for Div. 2)