题解【P5979 [PA2014]Druzyny】

KellyFrog · 2022-04-02 14:30:45 · 题解

模拟赛题，终于学会了 cdq 分治

朴素 DP 就是对于 \max_{j\le k\le i} l_k \le i-j+1\le \min_{j\le k\le i} r_k，f_j\rightarrow f_i

考虑如何优化，一般对 min/max 可以用单调栈或者分治解决，由于单调栈会让左右两边的边界发生变化，所以尝试使用 cdq 分治，问题转化为每次处理左边对右边的贡献

分别令 a_j,b_j 表示前一半的后缀 \max l 和 \min r、c_i,d_i 表示后一半的前缀 \max l 和 \min r，不难分类讨论 a_j,c_i 和 b_j,d_i 的大小关系，分为四类：

时间复杂度 O(n\log^2 n)，注意初始值要弄成 -inf，代码写的比较丑

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i, s, t) for(int i = (s); i <= (t); ++i)
#define per(i, s, t) for(int i = (t); i >= (s); --i)
#define fi first
#define se second
#define pb push_back
#define mp make_pair

const int N = 1e6 + 5;
const int M = N * 22;
const int P = 1e9 + 7;
const int inf = 0x3f3f3f3f;

int n, l[N], r[N];
int a[N], b[N], c[N], d[N], pa[N], vala[N], valb[N];
int posa[N], posb[N], pospa[N], pospb[N];
pair<int, int> f[N];
int rt[N], tt;

inline void upd(pair<int, int>& x, const pair<int, int>& y) {
    if(x.fi == y.fi) x.se = (x.se + y.se) % P;
    else if(x.fi < y.fi) x = y;
}

inline void upd2(pair<int, int>& x, pair<int, int> y) {
    ++y.fi;
    if(x.fi == y.fi) x.se = (x.se + y.se) % P;
    else if(x.fi < y.fi) x = y;
}

pair<int, int> inc(const pair<int, int>& x) { return mp(x.fi + 1, x.se); }

namespace seg1 {
    int ls[M], rs[M];
    pair<int, int> val[M];

    inline int newnode(int o) {
    ++tt;
    ls[tt] = ls[o];
    rs[tt] = rs[o];
    val[tt] = val[o];
    return tt;
    }

    inline void insert(int& o1, int& o2, int p, int l, int r) {
        o1 = newnode(o2);
    if(l == r) {
        assert(val[o1] == val[0]);
        val[o1] = f[p-1];
        return;
    }
    int mid = l + r >> 1;
    if(p <= mid) insert(ls[o1], ls[o2], p, l, mid);
    else insert(rs[o1], rs[o2], p, mid + 1, r);

    val[o1] = mp(-inf, 0);
    upd(val[o1], val[ls[o1]]);
    upd(val[o1], val[rs[o1]]);
    }

    inline pair<int, int> query(int o, int ql, int qr, int l, int r) {
    if(ql > qr) return mp(-inf, 0);
    if(!o) return mp(-inf, 0);
    if(ql <= l && r <= qr) {
        //cerr << "seg1 " << o << " " << l << " " << r << " " <<  val[o].fi << " " << val[o].se << "\n";
        return val[o];
    }
    int mid = l + r >> 1;
    pair<int, int> res = mp(-inf, 0);
    if(ql <= mid) upd(res, query(ls[o], ql, qr, l, mid));
    if(mid < qr) upd(res, query(rs[o], ql, qr, mid + 1, r));
    return res;
    }
}

namespace seg2 {
    pair<int, int> val[N<<2];
    inline void build(int o, int l, int r) {
    if(l == r) {
        val[o] = f[l-1];
        return;
    }
    int mid = l + r >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    val[o] = mp(-inf, 0);
    upd(val[o], val[o << 1]);
    upd(val[o], val[o << 1 | 1]);
    }

    inline pair<int, int> query(int o, int ql, int qr, int l, int r) {
    if(ql > qr) return mp(-inf, 0);
    if(ql <= l && r <= qr) return val[o];
    int mid = l + r >> 1;
    pair<int, int> res = mp(-inf, 0);
    if(ql <= mid) upd(res, query(o << 1, ql, qr, l, mid));
    if(mid < qr) upd(res, query(o << 1 | 1, ql, qr, mid + 1, r));
    return res;
    }
}

inline void solve(int l, int r) {
    if(l == r) {
    if(::l[l] <= 1) upd2(f[l], f[l-1]);
    return;
    }

    int mid = l + r >> 1;
    solve(l, mid);

    //cerr << "solve = " << l << ", " << mid << " -> " << mid + 1 << ", " << r << "\n";
    per(i, l, mid) {
    a[i] = max(a[i + 1], ::l[i]);
    b[i] = min(b[i + 1], ::r[i]);
    }
    rep(i, mid + 1, r) {
    c[i] = max(c[i - 1], ::l[i]);
    d[i] = min(d[i - 1], ::r[i]);
    }

    rep(i, l, mid) vala[i] = a[i] + i;
    rep(i, l, mid) valb[i] = b[i] + i;

    rep(i, mid + 1, r) {
    posa[i] = upper_bound(a + l, a + mid + 1, c[i], greater<int>()) - a;
    posb[i] = upper_bound(b + l, b + mid + 1, d[i]) - b;
    }

    // c[i] > a[j], d[i] < b[j]

    seg2::build(1, l, mid);
    rep(i, mid + 1, r) {
    int ql = l, qr = mid;
    ql = max<int>(ql, posb[i]);
    ql = max<int>(ql, posa[i]);
    ql = max(ql, i + 1 - d[i]);
    qr = min(qr, i + 1 - c[i]);
    upd2(f[i], seg2::query(1, ql, qr, l, mid));
    }

    //c[i] <= a[j], d[i] < b[j]

    auto compa = [&](int i, int j) { return vala[i] < vala[j]; };
    rep(i, l, mid) pa[i] = i;
    sort(pa + l, pa + mid + 1, compa);
    rep(i, l, mid) {
    seg1::insert(rt[i], rt[i-1], pa[i], l, mid);
    }

    rep(i, mid + 1, r) {
    vala[i] = i + 1;
    pospa[i] = upper_bound(pa + l, pa + mid + 1, i, compa) - pa;
    pospb[i] = lower_bound(valb + l, valb + mid + 1, i + 1) - valb;
    }

    rep(i, mid + 1, r) {
    int p = pospa[i] - 1;
    int ql = l, qr = mid;
    ql = max<int>(ql, posb[i]);
    ql = max(ql, i + 1 - d[i]);
    qr = min<int>(qr, posa[i] - 1);
    upd2(f[i], seg1::query(rt[p], ql, qr, l, mid));
    }
    //c[i] > a[j], d[i] >= b[j]
    rep(i, mid + 1, r) {
    int ql = l, qr = mid;
    ql = max<int>(ql, posa[i]);
    qr = min<int>(qr, posb[i] - 1);
    qr = min(qr, i + 1 - c[i]);
    ql = max<int>(ql, pospb[i]);
    upd2(f[i], seg2::query(1, ql, qr, l, mid));
    }

    rep(i, mid + 1, r) {
    int ql = l, qr = mid;
    qr = min<int>(qr, posa[i] - 1);
    qr = min<int>(qr, posb[i] - 1);
    ql = max<int>(ql, pospb[i]);

    int p = pospa[i] - 1;
    upd2(f[i], seg1::query(rt[p], ql, qr, l, mid));
    }

    rep(i, l, r) {
    vala[i] = valb[i] = a[i] = c[i] = 0;
    b[i] = d[i] = inf;
    rt[i] = 0;
    }
    tt = 0;

    solve(mid + 1, r);
}

int main() {
    // freopen("elect.in", "r", stdin);
    // freopen("elect.out", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n;
    rep(i, 1, n) cin >> l[i] >> r[i];
    rep(i, 1, n) f[i] = mp(-inf, 0);

    memset(b, 0x3f, sizeof b);
    memset(d, 0x3f, sizeof d);
    f[0] = mp(0, 1);
    seg1::val[0] = mp(-inf, 0);

    solve(1, n);

    if(f[n].fi <= 0) cout << "NIE" << "\n";
    else cout << f[n].fi << " " << f[n].se << "\n";
    cout.flush();

    return 0;
}