说一个 $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)$ 当且仅当：
- $j-i\in\operatorname{rng}(i,mid)$
- $j-i\in\operatorname{rng}(mid+1,j)$
注意到条件 1 与 $i$ 相关性较大，条件 2 与 $j$ 相关性比较大，考虑分别满足两个条件。
我们可以开一个下标线段树 $T$，然后枚举 $j\in[mid+1,r]$，每次进行三类操作：
- 对于所有满足 $j=i+\operatorname{mxl}(i,mid)-1$ 的 $i$，$T_i\gets dp_i+1$。
- 对于所有满足 $j=i+\operatorname{mnr}(i,mid)$ 的 $i$，$T_i\gets-\infty$。
- $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;
}
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: