专栏文章

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

CClaire0918
P12761题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjwigz
此快照首次捕获于
2025/12/02 03:37
3 个月前
此快照最后确认于
2025/12/02 03:37
3 个月前
查看原文
我们容易将问题转化为给定若干区间 [li,ri][l_i, r_i]，求至少需要放多少个点，使得每个区间内至少有一个点，并求方案数。
首先将所有 li,ril_i, r_i 离散化得到 {ai}\{a_i\}，我们发现本质不同的点只有两类：
  1. x=aix = a_i，这就是一个普通的点。
  2. x∈(ai−1,ai)x \in (a_{i - 1}, a_i)，我们将所有 ii 相同的 xx 当作一个点，但这实际上是 ai−ai−1−1a_i - a_{i - 1} - 1 个点，我们在答案上乘上该系数。
这样本质不同的点就仅有 O(n)\mathcal{O}(n) 个了。
设 fi=(x∈Z,y∈Z)f_i = (x \in \mathbb{Z}, y \in \mathbb{Z}) 表示仅考虑 ii 之前的点，选了 ii 且 ii 之前没有漏任何一个区间（即不存在 rk≤ir_k \leq i 且 [lk,rk][l_k, r_k] 没有被覆盖）的答案，转移考虑枚举 j<ij < i，jj 不合法当且仅当存在 [lk,rk][l_k, r_k] 使得 rk≤ir_k \leq i 且 lk>jl_k > j，从而 jj 合法当且仅当对于任何 rk≤ir_k \leq i 都有 j≥lkj \geq l_k。将 [lk,rk][l_k, r_k] 挂在 rkr_k 上，记录扫过的最大 lkl_k 即可求出 jj 的左端点。我们记其为 pp，就有
fi=∑j=pi−1fjf_i = \sum_{j = p}^{i - 1} f_j
这显然可以线段树维护，或者注意到其查询的是一段后缀的和，转化为前缀使用树状数组，时间复杂度 O(nlog⁡n)\mathcal{O}(n\log n)，但是常数很大。
我们发现 fif_i 中的最小点数随 ii 上升单调不降，于是能转移到 ii 的 jj 是以 pp 为左端点的一个区间，而且 pp 也是单调不降的，这启示我们使用单调队列维护，这样就仅有离散化中复杂度为 O(nlog⁡n)\mathcal{O}(n\log n)，转移复杂度降到了 O(n)\mathcal{O}(n)，常数减小很多。
Code：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...