黑白沙漠

题意

在黑白沙漠中有 $n$ 幢建筑，分别位于 $x_i$，且能够在大风中坚持 $y_i$ 单位时间而不倒塌。

初始时 $[L,R]$ 是无风区。随着时间的变化，无风区会缩小。无风区的长度会以 $1$ 每单位时间的速度缩小，直至缩至一个在 $[L,R]$ 中均匀随机生成的点 $M$ 处。在无风区缩小的过程中，$\dfrac{M-L}{R-M}$ 保持不变。

请对每一幢建筑，求出其成为最后一幢倒塌的建筑的概率。

解析

首先我们去除无意义的 $L$，令 $x\gets x-L, R\gets R - L$。对于第 $i$ 幢建筑物，其能够坚持的时间为

$$T_i(M)=\begin{cases} y_i+R\dfrac{R-x_i}{R-M}&\text{if } M < x_i\\ y_i+R\dfrac{x_i}{M}&\text{if } M > x_i \end{cases}$$

由于 $M<x_i$ 和 $M>x_i$ 的情况是对称的，我们考虑 $M<x_i$ 即可。

注意到 $T_i$ 表现出类反比例函数的形式，则有 $T_i^\prime(M)>0$ 且 $T_i^\prime(M)>T_{i+1}^\prime(M)$。这样，只要在某个点 $M_1$ 时有 $T_{i}(M_1)>T_{i+1}(M_1)$，则对任意 $M_2>M_1$，$T_{i}(M_2)>T_{i+1}(M_2)$ 也成立。

那么我们按 $x_i$ 从大到小将建筑物加入单调栈，则单调栈中的建筑的斜率是单调递增的。我们用类似决策单调性的方法得到使每个建筑开始成为最优的建筑的最小的 $M$ 即可。

实现

#include <bits/stdc++.h>
#define binary_search for(int _ = 0; _ < 40; ++_)

typedef long double real;
const int maxn = 2e5 + 19;
const real eps = 1e-6;

struct node{
    real l, r;
    int id;
};

int T, n, L, R, x[maxn], y[maxn];
std::vector<node> m_less_than_x, m_greater_than_x;
std::vector<std::pair<real, int> > tmp;
std::vector<real> all;
std::vector<std::pair<int, int> > max;
real begin[maxn], ans[maxn];
int st[maxn], top;

inline real f_1(int i, real m){
    return y[i] + R * real(R - x[i]) / real(R - m);
}

inline real f_2(int i, real m){
    return y[i] + R * real(x[i]) / real(m);
}

real bound_1(int i, int j){
    real l = 0, r = x[i];
    binary_search{
        real mid = (l + r) / 2;
        if(f_1(i, mid) >= f_1(j, mid)) r = mid;
        else l = mid;
    }
    return l;
}

real bound_2(int i, int j){
    real l = x[i], r = R;
    binary_search{
        real mid = (l + r) / 2;
        if(f_2(i, mid) >= f_2(j, mid)) l = mid;
        else r = mid;
    }
    return l;
}

inline bool cmp(const real &x, const real &y){
    return std::fabs(x - y) <= eps;
}

inline bool cmpl(const std::pair<real, int> &x, const std::pair<real, int> &y){
    return std::fabs(x.first - y.first) < eps ? x.second > y.second : x.first < y.first;
}

inline bool cmpg(const std::pair<real, int> &x, const std::pair<real, int> &y){
    return std::fabs(x.first - y.first) < eps ? x.second < y.second : x.first > y.first;
}

int main(){
    std::scanf("%d%d%d%d", &T, &n, &L, &R), R -= L;
    for(int i = 1; i <= n; ++i) std::scanf("%d", x + i), x[i] -= L;
    for(int i = 1; i <= n; ++i) std::scanf("%d", y + i);

    begin[n] = 0, st[top = 1] = n;
    for(int i = n - 1; i >= 1; --i){
        while(top > 1 && begin[st[top]] >= x[i])
            --top;
        while(top && bound_1(i, st[top]) <= begin[st[top]] + eps)
            begin[st[top--]] = x[i];
        if(top) begin[i] = bound_1(i, st[top]), st[++top] = i;
        else begin[i] = 0, st[++top] = i;
    }

    for(int i = 1; i <= n; ++i)
        if(std::fabs(begin[i] - x[i]) > eps)
            tmp.push_back(std::make_pair(begin[i], i)), tmp.push_back(std::make_pair(x[i], 0));
    std::sort(tmp.begin(), tmp.end(), cmpl);

    top = 0;
    for(int i = 0; i < (int)tmp.size(); ++i){
        if(tmp[i].second)
            st[++top] = tmp[i].second;
        while(top && x[st[top]] < tmp[i].first + eps)
            --top;
        if(top && i + 1 < (int)tmp.size())
            m_less_than_x.push_back((node){tmp[i].first, tmp[i + 1].first, st[top]});
    }

    tmp.clear();

    begin[1] = R, st[top = 1] = 1;
    for(int i = 2; i <= n; ++i){
        while(top > 1 && begin[st[top]] <= x[i])
            --top;
        while(top && bound_2(i, st[top]) >= begin[st[top]] - eps)
            begin[st[top--]] = x[i];
        if(top) begin[i] = bound_2(i, st[top]), st[++top] = i;
        else begin[i] = R, st[++top] = i;
    }

    for(int i = 1; i <= n; ++i)
        if(std::fabs(begin[i] - x[i]) > eps)
            tmp.push_back(std::make_pair(begin[i], i)), tmp.push_back(std::make_pair(x[i], 0));
    std::sort(tmp.begin(), tmp.end(), cmpg);

    top = 0;
    for(int i = 0; i < (int)tmp.size(); ++i){
        if(tmp[i].second)
            st[++top] = tmp[i].second;
        while(top && x[st[top]] > tmp[i].first - eps)
            --top;
        if(top && i + 1 < (int)tmp.size())
            m_greater_than_x.push_back((node){tmp[i + 1].first, tmp[i].first, st[top]});
    }

    for(int i = 0; i < (int)m_less_than_x.size(); ++i)
        all.push_back(m_less_than_x[i].l), all.push_back(m_less_than_x[i].r);
    for(int i = 0; i < (int)m_greater_than_x.size(); ++i)
        all.push_back(m_greater_than_x[i].l), all.push_back(m_greater_than_x[i].r);

    std::sort(all.begin(), all.end());
    all.resize(std::unique(all.begin(), all.end(), cmp) - all.begin());
    max.resize(all.size());

    for(int i = 0; i < (int)m_less_than_x.size(); ++i){
        int l = std::lower_bound(all.begin(), all.end(), m_less_than_x[i].l - eps * 2) - all.begin(),
            r = std::lower_bound(all.begin(), all.end(), m_less_than_x[i].r - eps * 2) - all.begin();
        for(int j = l; j < r; ++j)
            max[j].first = m_less_than_x[i].id;
    }

    for(int i = 0; i < (int)m_greater_than_x.size(); ++i){
        int l = std::lower_bound(all.begin(), all.end(), m_greater_than_x[i].l - eps * 2) - all.begin(),
            r = std::lower_bound(all.begin(), all.end(), m_greater_than_x[i].r - eps * 2) - all.begin();
        for(int j = l; j < r; ++j)
            max[j].second = m_greater_than_x[i].id;
    }

    for(int i = 0; i + 1 < (int)all.size(); ++i)
        if(max[i].first || max[i].second){
            if(!max[i].first || !max[i].second){
                ans[max[i].first + max[i].second] += all[i + 1] - all[i];
                continue;
            }
            real l = all[i], r = all[i + 1];
            binary_search{
                real mid = (l + r) / 2;
                if(f_1(max[i].first, mid) >= f_2(max[i].second, mid)) r = mid;
                else l = mid;
            }
            ans[max[i].first] += all[i + 1] - l;
            ans[max[i].second] += l - all[i];
        }

    for(int i = 1; i <= n; ++i) std::printf("%.10Lf\n", ans[i] / R);
    return 0;
}

来源

NOI.AC #2010 黑白沙漠

评论