【题解】P5979 [PA2014]Druzyny

说一个 $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因为这个转移的条件比较复杂，合法的 $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 打个标记即可。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118


#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;
}