4

【题解】P5979 [PA2014]Druzyny

 3 years ago
source link: https://blog-e.tk/2022/04/03/%E9%A2%98%E8%A7%A3-P5979-PA2014-Druzyny/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

【题解】P5979 [PA2014]Druzyny

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

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

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

dpi=1+max⁡[j<i]∧[(i−j)∈rng⁡(i+1,j)]dpjdp_i=1+\max_{[j<i]\land [(i-j)\in\operatorname{rng}(i+1,j)]}dp_jdpi​=1+[j<i]∧[(i−j)∈rng(i+1,j)]max​dpj​

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

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

dpi(i≤mid)dp_i(i\le mid)dpi​(i≤mid) 可以更新 dpj(j>mid)dp_j(j>mid)dpj​(j>mid) 当且仅当：

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

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

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

  1. 对于所有满足 j=i+mxl⁡(i,mid)−1j=i+\operatorname{mxl}(i,mid)-1j=i+mxl(i,mid)−1 的 iii，Ti←dpi+1T_i\gets dp_i+1Ti​←dpi​+1。
  2. 对于所有满足 j=i+mnr⁡(i,mid)j=i+\operatorname{mnr}(i,mid)j=i+mnr(i,mid) 的 iii，Ti←−∞T_i\gets-\inftyTi​←−∞。
  3. dpj←min⁡j∈[j−mnr⁡(mid+1,r),j−mxl⁡(mid+1,r)]dp_j\gets\min_{j\in[j-\operatorname{mnr}(mid+1,r),j-\operatorname{mxl}(mid+1,r)]}dpj​←minj∈[j−mnr(mid+1,r),j−mxl(mid+1,r)]​。

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

具体实现就比较好搞了，可以先扫一下 i∈[l,mid]i\in[l,mid]i∈[l,mid]，然后其对应进行 1，2 操作的 jjj 处开 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
本文为作者原创，转载请注明出处：本文链接


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK