[Medium-Hard] P11733 [集训队互测 2015] 上帝之手

xiezheyuan2025/2/18约 1705 字大约 9 分钟

简要题意

注意这里的题意使用的字母相比于原题意的字母略有改动，本题解中以这里的字母为准。

给定两个长度为 $n$ 的序列 $d,l$ 。若第 $i-1$ 个时刻权值为 $x_{i-1}$ ，则 $x_i\gets\min(x_{i-1}+d_i,l_i)$ 。有 $m$ 次操作，支持：

0 p v 表示 $l_p\gets v$ 。
1 L R k 对于全体 $c\in[L,R]$ ，令 $x_{c-1}\gets l_{c-1}$ ，从第 $c$ 个时刻开始到第 $R$ 个时刻，求出最终的 $x_R$ 的第 $k$ 大值。
2 L R x0 对于全体 $c\in[L,R]$ ，令 $x_{c-1}\gets x_0$ ，从第 $c$ 个时刻开始到第 $R$ 个时刻，求出最终的 $x_R$ 的最大值。
3 L R 对于全体 $c\in[L,R]$ ，令 $x_{c-1}\gets l_{c-1}$ ，从第 $c$ 个时刻开始到第 $R$ 个时刻，求出最终 $x_R$ 的种类数。

$1\leq n\leq 10^5,1\leq m\leq 2\times 10^5,0\leq d_i\leq 10^4,0\leq l_i\leq 10^9$ 。

思路

DS trick 多合一，不可多得的练习题。

Part 1

先来考虑如何快速求出对于一个 $c$ ，从第 $c$ 个时刻开始，最终的 $x_R$ 。这并不困难，直接给出式子：

\min\left(x_{c-1}+\sum_{k=c}^{R} d_k, \min_{k=c+1}^{R+1}l_{k-1}+\sum_{i=k}^{R}d_i\right)

大致就是要么没有受到上界的性质，要么枚举最后受到上界限制的点 $k-1$ 。由于所有可能情况都可以取到，我们每次更新 $x_i$ 只会选择最小的方案，所以需要取 $\min$ 。

于是预处理 $d$ 的前缀和，然后记一个 $F_k=l_{k-1}+\sum_{i=k}^{n}d_i$ 的 RMQ（由于带修改，所以需要动态化，可以用线段树之类的），就可以做到单次询问 $O(n\log n)$ 了。

Part 2

考虑如何快速做第一种询问。我们发现 $x_{c-1}\gets l_{c-1}$ ，所以对于每一个 $c$ ，结合 Part 1， $x_R$ 其实就是 $F$ 在区间 $[c,R+1]$ 的最小值减去 $d$ 的一个后缀和（这是常量）。

由于最小值单调不增，所以对于 $c<c'$ ，后者求出的 $x_R$ 更大。于是第 $k$ 大其实就是在 $c=R-k+1$ 处取到，于是转换为单点修改区间最大值问题，用普通的线段树即可解决。时间复杂度单次 $O(\log n)$ 。

Part 3

现在的任务是第二种询问，此时 $x_{c-1}$ 不再是 $l_{c-1}$ ，但是求第 $k$ 大改为了求最大值。这需要我们再次观察式子：

\min\left(x_{c-1}+\sum_{k=c}^{R} d_k, \min_{k=c+1}^{R+1}l_{k-1}+\sum_{i=k}^{R}d_i\right)

观察到 $\min$ 的第一个参数， $f(c)=x_0+\sum_{k=c}^{R}d_k$ 关于 $c$ 不增，第二个参数 $g(c)=\min_{k=c+1}^{R+1} F_k-\Delta$ （其中 $\Delta=\sum_{k=R+1}^{n}d_k$ 为常量）关于 $c$ 不降。

对于两个单调的且增减性不同的函数的最小值求最大值，一般用二分，找到它们的交点，则答案在交点取到（当然，如果没有整交点，则在交点两侧取到）。特别地，如果没有交点，则在某一个边界取到。

时间复杂度 $O(\log^2 n)$ （一个 $\log$ 在二分，另一个 $\log$ 在求函数 $g(c)$ 的值）。

Part 4

最后需要解决的是第三种询问，我们需要求出种类数， $x_{c-1}\gets l_{c-1}$ 。由于 $x_{c-1}$ 与第一种询问相同，所以可以沿用处理第一种询问时得到的结论：对于每一个 $c$ ， $x_R$ 是 $F$ 在区间 $[c,R+1]$ 的最小值减去 $d$ 的一个后缀和。

于是我们需要单点修改 $F$ 上的一个位置，查询某一个区间的后缀最小值的种类数。参考 P4198 楼房重建，使用兔队线段树完成即可。具体可以参考兔队的博客。

时间复杂度单次 $O(\log^2 n)$ 。

故总时间复杂度 $O(n\log^\mu n+m\log^2 n)$ 可以通过本题（其中 $\mu$ 视实现可能为 $1$ 或 $2$ ）。

代码

#include <bits/stdc++.h>
#define ls (i << 1)
#define rs (i << 1 | 1)
using namespace std;

const int N = 1e5 + 5;

template<class T, int N>
struct pinkrabbit_sgt {
    T t[N << 2];
    int cnt[N << 2];

    void build(int i, int l, int r){
        cnt[i] = 1;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
    }

    int calc(T v, int i, int l, int r){
        if(l == r) return t[i] < v;
        int mid = (l + r) >> 1;
        if(t[rs] < v) return calc(v, rs, mid + 1, r) + cnt[i] - cnt[rs];
        return calc(v, ls, l, mid);
    }

    void update(int p, T v, int i, int l, int r){
        if(l == r) return t[i] = v, void();
        int mid = (l + r) >> 1;
        if(p <= mid) update(p, v, ls, l, mid);
        else update(p, v, rs, mid + 1, r);
        t[i] = std::min(t[ls], t[rs]);
        cnt[i] = cnt[rs] + calc(t[rs], ls, l, mid);
    }

    void split(int ql, int qr, vector<tuple<int,int,int>>& vct, int i, int l, int r){
        if(ql <= l && r <= qr) return vct.emplace_back(i, l, r), void();
        int mid = (l + r) >> 1;
        if(ql <= mid) split(ql, qr, vct, ls, l, mid);
        if(mid < qr) split(ql, qr, vct, rs, mid + 1, r);
    }

    T min(int ql, int qr, int i, int l, int r){
        vector<tuple<int,int,int>> vct;
        split(ql, qr, vct, i, l, r);
        T ret = numeric_limits<T>::max();
        for(auto [i, l, r] : vct) ret = std::min(ret, t[i]);
        return ret;
    }

    int variants(int ql, int qr, int i, int l, int r){
        vector<tuple<int,int,int>> vct;
        split(ql, qr, vct, i, l, r), reverse(vct.begin(), vct.end());
        int ret = cnt[get<0>(vct[0])], lst = t[get<0>(vct[0])];
        for(size_t i=1;i<vct.size();i++){
            auto [u, l, r] = vct[i];
            ret += calc(lst, u, l, r), lst = std::min(lst, t[u]);
        }
        return ret;
    }
};

int n, m, D[N], L[N], F[N];
pinkrabbit_sgt<int, N> sgt;

void update(int p, int v){ sgt.update(p + 1, F[p + 1] = (D[p + 1] + (L[p] = v)), 1, 1, n + 1); }

int query1(int _, int r, int k){ return sgt.min(r - k + 1, r + 1, 1, 1, n + 1) - D[r + 1]; }

int query2(int l, int r, int x0){
    auto f = [=](int c){ return x0 + D[c] - D[r + 1]; };
    auto g = [=](int c){ return sgt.min(c + 1, r + 1, 1, 1, n + 1) - D[r + 1]; };
    int L = l, R = r;
    while(L < R){
        int mid = (L + R) >> 1;
        if(g(mid) >= f(mid)) R = mid;
        else L = mid + 1;
    }
    if(g(L) >= f(L)) return max(min(f(L), g(L)), L == l ? INT_MIN : min(f(L - 1), g(L - 1)));
    return max(min(f(l), g(l)), min(f(r), g(r)));
}

int query3(int l, int r){ return sgt.variants(l, r + 1, 1, 1, n + 1) - (F[r] < F[r + 1]); }

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    sgt.build(1, 1, n + 1);
    for(int i=1;i<=n;i++) cin >> D[i];
    for(int i=n;~i;i--) D[i] += D[i + 1];
    for(int i=0;i<=n;i++) cin >> L[i];
    for(int i=1;i<=n+1;i++) sgt.update(i, F[i] = L[i - 1] + D[i], 1, 1, n + 1);
    while(m--){
        int op, x, y, z; cin >> op >> x >> y;
        switch(op){
            case 0: update(x, y); break;
            case 1: cin >> z, cout << query1(x, y, z) << '\n'; break;
            case 2: cin >> z, cout << query2(x, y, z) << '\n'; break;
            case 3: cout << query3(x, y) << '\n'; break;
        }
    }
    return 0;
}

// Written by xiezheyuan

Submission。