自动搬运

查看原文

来自洛谷，原作者为

	Iniaugoty 我一定会进盐中校队！！！！！11111

搬运于2025-08-24 23:17:56，当前版本为作者最后更新于2025-06-24 00:17:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不妨先抛开计数不谈，想想这个经典的贪心题有没有什么别的性质不那么强的做法。

为了便于讨论，在 $[i, i + 1]$ 上查票称为选第 $i$ 个点。

考虑 DP。设 $f _ i$ 为考虑完 $[1, i]$，强制选 $i$ ，最少选多少点。枚举上一个选的点 $j$ 进行转移，$f _ i \gets f _ j + 1$。

这个 $j$ 需要满足什么条件，不存在某个路线 $[a _ k, b _ k]$，使得 $j < a _ k < b _ k \le i$（如果存在的话，这个区间没有被任何点覆盖）。也就是说，记 $l _ i = \displaystyle \max _ {b _ k \le i} a _ k$，要求 $j \ge l _ i$。

$l _ i$ 可以轻易地处理出来，这样这个做法是 $O(m ^ 2)$ 的。因为跟区间长度没有关系，把 $a _ k, b _ k, m$ 丢到一起离散化，可以做到 $O(n ^ 2)$。

注意到转移形如单点修改，求区间 $\min$。使用线段树维护，可以优化到 $O(n \log n)$。

方案数可以相当容易地和最小值一起维护的。但需要注意的是，离散化后的一个点实际上相当于原图的一段区间，这一段区间中每个点是等价的，在转移后还要乘上区间长度。

#include <bits/stdc++.h>
#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define dF(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, LL> pii;
const int N = 1e6 + 5;
const int P = 1e9 + 7;

int m, n, a[N], b[N], k, c[N], l[N]; pii dp[N];
int Add(int x, int y) { return x + y >= P ? x + y - P : x + y; }

pii t[N << 2];
pii W(pii x, pii y) {
  auto [tl, sl] = x; auto [tr, sr] = y;
  if (tl < tr) return {tl, sl};
  else if (tr < tl) return {tr, sr};
  else return {tl, Add(sl, sr)};
}
void Pushup(int u) { t[u] = W(t[u << 1], t[u << 1 | 1]); }
void Update(int x, pii k, int l, int r, int u) {
  if (l == r) return t[u] = k, void();
  int mid = l + r >> 1;
  if (x <= mid) Update(x, k, l, mid, u << 1);
  else Update(x, k, mid + 1, r, u << 1 | 1);
  Pushup(u);
}
pii Query(int ql, int qr, int l, int r, int u) {
  if (ql <= l && r <= qr) return t[u];
  int mid = l + r >> 1; pii res = {N, 0};
  if (ql <= mid) res = W(res, Query(ql, qr, l, mid, u << 1));
  if (qr > mid) res = W(res, Query(ql, qr, mid + 1, r, u << 1 | 1));
  return res;
}

void mian() {
  cin >> m >> n, c[1] = 0, c[k = 2] = m;
  F(i, 1, n) cin >> a[i] >> b[i], c[++k] = a[i], c[++k] = b[i];
  sort(c + 1, c + k + 1), k = unique(c + 1, c + k + 1) - c - 1;
  F(i, 1, n)
    a[i] = lower_bound(c + 1, c + k + 1, a[i]) - c,
    b[i] = lower_bound(c + 1, c + k + 1, b[i]) - c - 1;
  F(i, 1, k) l[i] = 1;
  F(i, 1, n) l[b[i]] = max(l[b[i]], a[i]);
  F(i, 1, k << 2) t[i] = {N, 0};
  Update(1, dp[1] = {0, 1}, 1, k, 1);
  int lim = 1;
  F(i, 2, k - 1)
    dp[i] = Query(lim, i - 1, 1, k, 1),
    ++dp[i].first, dp[i].second = 1ll * dp[i].second * (c[i + 1] - c[i]) % P,
    Update(i, dp[i], 1, k, 1), lim = max(lim, l[i]);
  dp[k] = Query(lim, k - 1, 1, k, 1);
  cout << dp[k].first << " " << dp[k].second << "\n";
}

int main() {
  // freopen("zyq.in", "r", stdin);
  // freopen("zyq.out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _; cin >> _; while (_--) mian();
  return 0;
}