题解：P12761 [POI 2018 R2] 列车员 Conductor

· · 题解

我们容易将问题转化为给定若干区间 [l_i, r_i]，求至少需要放多少个点，使得每个区间内至少有一个点，并求方案数。

首先将所有 l_i, r_i 离散化得到 \{a_i\}，我们发现本质不同的点只有两类：

这样本质不同的点就仅有 \mathcal{O}(n) 个了。

设 f_i = (x \in \mathbb{Z}, y \in \mathbb{Z}) 表示仅考虑 i 之前的点，选了 i 且 i 之前没有漏任何一个区间（即不存在 r_k \leq i 且 [l_k, r_k] 没有被覆盖）的答案，转移考虑枚举 j < i，j 不合法当且仅当存在 [l_k, r_k] 使得 r_k \leq i 且 l_k > j，从而 j 合法当且仅当对于任何 r_k \leq i 都有 j \geq l_k。将 [l_k, r_k] 挂在 r_k 上，记录扫过的最大 l_k 即可求出 j 的左端点。我们记其为 p，就有

f_i = \sum_{j = p}^{i - 1} f_j

这显然可以线段树维护，或者注意到其查询的是一段后缀的和，转化为前缀使用树状数组，时间复杂度 \mathcal{O}(n\log n)，但是常数很大。

我们发现 f_i 中的最小点数随 i 上升单调不降，于是能转移到 i 的 j 是以 p 为左端点的一个区间，而且 p 也是单调不降的，这启示我们使用单调队列维护，这样就仅有离散化中复杂度为 \mathcal{O}(n\log n)，转移复杂度降到了 \mathcal{O}(n)，常数减小很多。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

namespace IO{
    #define SIZ (1 << 18)
    char ibuf[SIZ], *p1 = nullptr, *p2 = nullptr;
    #define gc() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, SIZ, stdin), p1 == p2) ? EOF : *p1++)
    template <typename tp>
    void rd(tp &x){
        x = 0;
        int f = 1;
        char c = gc();
        for (;!isdigit(c); c == '-' && (f = -1), c = gc());
        for (;isdigit(c); x = x * 10 + (c ^ 48), c = gc());
        x *= f;
    }
    template <typename tp, typename... Arg>
    inline void rd(tp &x, Arg &...args){
        rd(x), rd(args...);
    }
    char obuf[SIZ], *p3 = obuf;
    inline void flush(){
        fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf;
    }
    inline void pc(const char c){
        p3 - obuf == SIZ && (flush(), 1538), *p3++ = c;
    }
    template <typename tp>
    void prt(tp x, char ed = '\n'){
        x < 0 && (pc('-'), x = -x);
        static char stk[40];
        int stkp = 0;
        do{
            stk[stkp] = char(x % 10), x /= 10, ++stkp;
        } while (x);
        while (stkp){
            pc(char(stk[--stkp] + '0'));
        }
        pc(ed);
    }
    #undef gc
    #undef SIZ
}

using namespace IO;

const int maxn = 1e6 + 10, mod = 1e9 + 7;

int t, n;
int a[maxn], b[maxn];
pair<int, int> f[maxn << 2];
vector<int> tmp, ad[maxn << 2];
deque<int> q;

inline int pos(int x){
    return lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();
}

template<typename Tp_x, typename Tp_y>
inline int mod_add(Tp_x x, Tp_y y){
    return x += y, x >= mod ? x -= mod : x;
}

template<typename Tp_x, typename Tp_y>
inline int self_mod_add(Tp_x &x, Tp_y y){
    return x = mod_add(x, y);
}

template<typename Tp, typename... Arg>
inline int mod_add(Tp x, Arg ...args){
    return x += mod_add(args...), x >= mod ? x -= mod : x;
}

pair<int, int> operator + (const pair<int, int> & a, const pair<int, int> & b){
    return a.first == b.first ? make_pair(a.first, mod_add(a.second, b.second)) : a.first < b.first ? a : b;
}

int main(){
    rd(t);
    while (t--){
        rd(n, n), tmp.clear();
        for (;!q.empty(); q.pop_back());
        for (int i = 1; i <= n; i++){
            rd(a[i], b[i]), b[i]--, tmp.push_back(a[i]), tmp.push_back(b[i]);
        }
        tmp.push_back(0), sort(tmp.begin(), tmp.end()), tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
        for (int i = 1; i <= n; i++){
            a[i] = pos(a[i]) << 1, b[i] = pos(b[i]) << 1, ad[b[i]].push_back(a[i]);
        }
        f[0] = make_pair(0, 1), q.push_back(0);
        int l = 0;
        pair<int, int> now = make_pair(0, 1);
        for (int i = 1; i <= tmp.size() - 1 << 1; i++){
            for (;!q.empty() && q.front() < l; self_mod_add(now.second, mod - f[q.front()].second), q.pop_front());
            q.empty() && (q.push_back(l), now = f[l], 1538);
            for (;q.back() < i - 1 && f[q.back() + 1].first == f[q.back()].first; q.push_back(q.back() + 1), self_mod_add(now.second, f[q.back()].second));
            f[i] = now, f[i].first++, f[i].second = (long long)f[i].second * (i & 1 ? tmp[i + 1 >> 1] - tmp[i >> 1] - 1 : 1) % mod;
            for (auto x: ad[i]){
                l = max(l, x);
            }
        }
        now = make_pair(1e9, 0);
        for (int i = l; i <= tmp.size() - 1 << 1; now = now + f[i], i++);
        prt(now.first, ' '), prt(now.second);
        for (int i = 1; i <= n; ad[b[i++]].clear());
    }
    flush();

return 0;
}