自动搬运

查看原文

来自洛谷，原作者为

	ethan_zhou 博客：blog-e.top

搬运于2025-08-24 22:16:10，当前版本为作者最后更新于2022-04-03 17:18:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

说一个 $O(n\log^2 n)$ 的 cdq 分治做法，常数不大，不用分类讨论，较为好写。

一些符号

• 记 $\operatorname{mxl}(l,r)$ 表示下标在 $l$ 到 $r$ 之间的所有区间的左端点最大值，$\operatorname{mnr}(l,r)$ 意义类似。
• 记 $\operatorname{rng}(l,r)=[\operatorname{mxl}(l,r),\operatorname{mnr}(l,r)]$。

暴戾

首先是一个简单的 $O(n^2)$ dp：

$$dp_i=1+\max_{[j<i]\land [(i-j)\in\operatorname{rng}(i+1,j)]}dp_j $$

因为这个转移的条件比较复杂，合法的 $j$ 都是不连续的，考虑用 cdq 分治来做。

cdq

假设我们目前已经知道 $dp_{[l, mid]}$，考虑这些 dp 值对 $dp_{[mid+1, r]}$ 的贡献。

$dp_i(i\le mid)$ 可以更新 $dp_j(j>mid)$ 当且仅当：

1. $j-i\in\operatorname{rng}(i,mid)$
2. $j-i\in\operatorname{rng}(mid+1,j)$

注意到条件 1 与 $i$ 相关性较大，条件 2 与 $j$ 相关性比较大，考虑分别满足两个条件。

我们可以开一个下标线段树 $T$，然后枚举 $j\in[mid+1,r]$，每次进行三类操作：

1. 对于所有满足 $j=i+\operatorname{mxl}(i,mid)-1$ 的 $i$，$T_i\gets dp_i+1$。
2. 对于所有满足 $j=i+\operatorname{mnr}(i,mid)$ 的 $i$，$T_i\gets-\infty$。
3. $dp_j\gets\min_{j\in[j-\operatorname{mnr}(mid+1,r),j-\operatorname{mxl}(mid+1,r)]}$。

前 2 种操作保证只有满足 条件 1 的 $i$ 此时才会在线段树里。 而第 3 个操作则从线段树中筛选出满足 条件 2 的 $i$ 用来更新 $dp_j$。

具体实现就比较好搞了，可以先扫一下 $i\in[l,mid]$，然后其对应进行 1，2 操作的 $j$ 处开 vector 打个标记即可。

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using pi = pair<int, int>;
const char nl = '\n';
const int MXN = 1e6 + 5, INF = 1e9, P = 1e9 + 7;
int n;
pi rng[MXN];
inline void upd(pi &x, const pi &y) {
    x.fi = max(x.fi, y.fi);
    x.se = min(x.se, y.se);
}
namespace segt {
struct node {
    int mx, mxc;
    node(int mx = -INF, int mxc = 0) : mx(mx), mxc(mxc) {}
} t[MXN << 2];
inline int norm(int x) { return x < P ? x : x - P; }
inline node operator+(const node &x, const node &y) {
    if (x.mx == y.mx) return node(x.mx, norm(x.mxc + y.mxc));
    if (x.mx > y.mx) return x;
    return y;
}
#define ls p << 1
#define rs p << 1 | 1
inline void pull(int p) { t[p] = t[ls] + t[rs]; }
void _mdf(int p, int l, int r, int mi, const node &mv) {
    if (l == r) {
        t[p] = mv;
        return;
    }
    int mid = (l + r) >> 1;
    if (mi <= mid)
        _mdf(ls, l, mid, mi, mv);
    else
        _mdf(rs, mid + 1, r, mi, mv);
    pull(p);
}
node _qry(int p, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return node();
    if (ql <= l && r <= qr) return t[p];
    int mid = (l + r) >> 1;
    return _qry(ls, l, mid, ql, qr) + _qry(rs, mid + 1, r, ql, qr);
}
int sz;
void init(int _sz) {
    sz = _sz;
    fill(t + 1, t + 1 + (sz << 2), node());
}
void mdf(int mi, const node &mv) { _mdf(1, 1, sz, mi, mv); }
node qry(int ql, int qr) { return _qry(1, 1, sz, ql, qr); }
} // namespace segt

using segt::init;
using segt::mdf;
using segt::qry;
vector<pi> id[MXN];
segt::node dp[MXN];
void solve(int l, int r) {
    if (r - l <= 50) {
        for (int i = l; i <= r; i++) {
            pi tmp = {1, n};
            for (int j = i - 1; j >= l; j--) {
                upd(tmp, rng[j + 1]);
                if (i - j > tmp.se) break;
                if (i - j >= tmp.fi) dp[i] = dp[i] + segt::node(dp[j].mx + 1, dp[j].mxc);
            }
        }
        return;
    }
    int mid = (l + r) >> 1;
    solve(l, mid);
    pi tmp = {1, n};
    for (int i = mid + 1; i <= r; i++) id[i].clear();
    for (int i = mid; i >= l; i--) {
        if (tmp.se < tmp.fi || i + tmp.se <= mid) break;
        if (i + tmp.fi <= r) {
            id[max(mid + 1, i + tmp.fi)].push_back({i, 1});
            id[min(r + 1, i + tmp.se + 1)].push_back({i, 0});
        }
        upd(tmp, rng[i]);
    }
    init(mid - l + 1);
    tmp = {1, n};
    for (int i = mid + 1; i <= r; i++) {
        for (auto j : id[i]) {
            if (j.se)
                mdf(j.fi - l + 1, dp[j.fi]);
            else
                mdf(j.fi - l + 1, segt::node());
        }
        upd(tmp, rng[i]);
        if (tmp.se < tmp.fi || i - tmp.se > mid) break;
        segt::node res = qry(max(l, i - tmp.se) - l + 1, min(mid, i - tmp.fi) - l + 1);
        ++res.mx;
        dp[i] = dp[i] + res;
    }
    solve(mid + 1, r);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    pi tmp = {1, n};
    for (int i = 1; i <= n; i++) {
        cin >> rng[i].fi >> rng[i].se;
        upd(tmp, rng[i]);
    }
    dp[0] = {0, 1};
    solve(0, n);
    if (dp[n].mx < 0)
        cout << "NIE";
    else
        cout << dp[n].mx << " " << dp[n].mxc;

    return 0;
}