rt. 不建树不预先打标记直接过。

错误但通过的代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define lson (k << 1)
#define rson (k << 1 | 1)
typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int L = 11;
int n, K, A[maxn << 3], f[L][L];
void ckadd(int& a, int b) { a += b; if (a >= mod) a -= mod; }
void ckmul(int& a, int b) { a = (ll)a * b % mod; }
int A1(int a, int b) { a += b; if (a >= mod) a -= mod; return a; }
struct Node {
	int a[L]{}; Node(int S = 0) { a[0] = S; }
	Node operator+(const Node& r) const {
		Node c; for (int i = 0; i <= K; i++) c.a[i] = A1(a[i], r.a[i]);
		return c;
	}
	void operator+=(const Node& r) {
		for (int i = 0; i <= K; i++) ckadd(a[i], r.a[i]);
	}
} c[maxn << 3];
vector<pair<int, int> > g;
void pushdown(int k) {
	if (A[k] != 1) {
		ckmul(A[lson], A[k]); ckmul(A[rson], A[k]);
		for (int i = 0; i <= K; i++)
			ckmul(c[lson].a[i], A[k]), ckmul(c[rson].a[i], A[k]);
		A[k] = 1;
	}
}
void add(int k, int l, int r, int p, Node v) {
	if (l == r) { c[k] += v; return; }
	int mid = (l + r) >> 1; pushdown(k);
	if (p <= mid) add(lson, l, mid, p, v);
	else add(rson, mid + 1, r, p, v);
	c[k] = c[lson] + c[rson];
}
void update(int k, int l, int r, int L, int R) {
	if (L <= l && r <= R) { ckadd(A[k], A[k]); c[k] += c[k]; return; }
	int mid = (l + r) >> 1; pushdown(k);
	if (L <= mid) update(lson, l, mid, L, R);
	if (R > mid) update(rson, mid + 1, r, L, R);
	c[k] = c[lson] + c[rson];
}
Node query(int k, int l, int r, int L, int R) {
	if (L <= l && r <= R) return c[k];
	int mid = (l + r) >> 1; pushdown(k); Node res;
	if (L <= mid) res += query(lson, l, mid, L, R);
	if (R > mid) res += query(rson, mid + 1, r, L, R);
	return res;
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> K; g.resize(n);
	for (auto& [l, r] : g) cin >> l >> r;
	sort(g.begin(), g.end());
	for (int i = 0; i <= K; i++) f[i][0] = 1;
	for (int i = 1; i <= K; i++)
		for (int j = 1; j <= i; j++)
			f[i][j] = A1(f[i - 1][j], f[i - 1][j - 1]);
	add(1, 0, n << 1, 0, Node(1));
	for (auto [l, r] : g) {
		Node cur = query(1, 0, n << 1, 0, l - 1), res;
		for (int i = 0; i <= K; i++)
			for (int j = 0; j <= i; j++)
				res.a[i] = (res.a[i] + (ll)cur.a[j] * f[i][j]) % mod;
		cur = query(1, 0, n << 1, l, r - 1);
		res += cur; add(1, 0, n << 1, r, res);
		if (r + 1 <= (n << 1)) update(1, 0, n << 1, r + 1, n << 1);
	} cout << query(1, 0, n << 1, 0, n << 1).a[K] << '\n';
	return 0;
}

正确的代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define lson (k << 1)
#define rson (k << 1 | 1)
typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int L = 11;
int n, K, A[maxn << 3], f[L][L];
void ckadd(int& a, int b) { a += b; if (a >= mod) a -= mod; }
void ckmul(int& a, int b) { a = (ll)a * b % mod; }
int A1(int a, int b) { a += b; if (a >= mod) a -= mod; return a; }
struct Node {
	int a[L]{}; Node(int S = 0) { a[0] = S; }
	Node operator+(const Node& r) const {
		Node c; for (int i = 0; i <= K; i++) c.a[i] = A1(a[i], r.a[i]);
		return c;
	}
	void operator+=(const Node& r) {
		for (int i = 0; i <= K; i++) ckadd(a[i], r.a[i]);
	}
} c[maxn << 3];
vector<pair<int, int> > g;
void pushdown(int k) {
	if (A[k] != 1) {
		ckmul(A[lson], A[k]); ckmul(A[rson], A[k]);
		for (int i = 0; i <= K; i++)
			ckmul(c[lson].a[i], A[k]), ckmul(c[rson].a[i], A[k]);
		A[k] = 1;
	}
}
void build(int k, int l, int r) {
	A[k] = 1; if (l == r) return;
	int mid = (l + r) >> 1;
	build(lson, l, mid); build(rson, mid + 1, r);
}
void add(int k, int l, int r, int p, Node v) {
	if (l == r) { c[k] += v; return; }
	int mid = (l + r) >> 1; pushdown(k);
	if (p <= mid) add(lson, l, mid, p, v);
	else add(rson, mid + 1, r, p, v);
	c[k] = c[lson] + c[rson];
}
void update(int k, int l, int r, int L, int R) {
	if (L <= l && r <= R) { ckadd(A[k], A[k]); c[k] += c[k]; return; }
	int mid = (l + r) >> 1; pushdown(k);
	if (L <= mid) update(lson, l, mid, L, R);
	if (R > mid) update(rson, mid + 1, r, L, R);
	c[k] = c[lson] + c[rson];
}
Node query(int k, int l, int r, int L, int R) {
	if (L <= l && r <= R) return c[k];
	int mid = (l + r) >> 1; pushdown(k); Node res;
	if (L <= mid) res += query(lson, l, mid, L, R);
	if (R > mid) res += query(rson, mid + 1, r, L, R);
	return res;
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> K; g.resize(n);
	for (auto& [l, r] : g) cin >> l >> r;
	sort(g.begin(), g.end());
	for (int i = 0; i <= K; i++) f[i][0] = 1;
	for (int i = 1; i <= K; i++)
		for (int j = 1; j <= i; j++)
			f[i][j] = A1(f[i - 1][j], f[i - 1][j - 1]);
	build(1, 0, n << 1); add(1, 0, n << 1, 0, Node(1));
	for (auto [l, r] : g) {
		Node cur = query(1, 0, n << 1, 0, l - 1), res;
		for (int i = 0; i <= K; i++)
			for (int j = 0; j <= i; j++)
				res.a[i] = (res.a[i] + (ll)cur.a[j] * f[i][j]) % mod;
		cur = query(1, 0, n << 1, l, r - 1);
		res += cur; add(1, 0, n << 1, r, res);
		if (r + 1 <= (n << 1)) update(1, 0, n << 1, r + 1, n << 1);
	} cout << query(1, 0, n << 1, 0, n << 1).a[K] << '\n';
	return 0;
}

区别在是否调用build函数。