自动搬运

查看原文

来自洛谷，原作者为

	PengAo AFO | 传奇五连铜

搬运于2025-08-24 22:56:43，当前版本为作者最后更新于2025-01-08 12:02:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题意简述：给定一个长为 $k$ 的初始数组 $\lbrace a_i \rbrace$，依次进行 $n$ 次操作 $(p_t, \lbrace b_{t,i} \rbrace)$：如果当前的 $a_{p_t}$ 小于 $b_{t,p_t}$，则将整个 $\lbrace a_i \rbrace$ 替换为 $\lbrace b_{t,i} \rbrace$，否则维持 $\lbrace a_i \rbrace$ 不变。输出 $n$ 次操作后的 $\lbrace a_i \rbrace$。$q$ 次询问，每次询问会给出 $\lbrace a_i \rbrace$ 的不同初始值。$n,q \le 10^5, k \le 20$。

不难想到暴力模拟上面的过程，时间复杂度最坏 $\mathcal{O}(qnk)$；每次修改由记录具体的 $\lbrace a_i \rbrace$ 改为记录上一次替换的位置，可以优化至 $\mathcal{O}(qn)$。仍无法通过本题。

考虑优化。在上面的做法中，如果发生了 $\lbrace a_i \rbrace \leftarrow \lbrace b_{t,i} \rbrace$ 的替换，我们发现最终 $\lbrace a_i \rbrace$ 的值将只和 $t$ 有关。令此时 $\lbrace a_i \rbrace$ 最后被替换成了 $\lbrace b_{x_t,i} \rbrace$。我们可以在预处理时倒序枚举 $t$，对于每个 $t$ 暴力向后遍历第一个能替换 $\lbrace b_{t,i} \rbrace$ 的 $\lbrace b_{t',i} \rbrace$，并将 $x_t$ 用 $x_{t'}$ 更新；若找不到这样的 $t'$，则 $x_t = t$。对于每个询问，也暴力找到第一个能替换 $\lbrace a_i \rbrace$ 的 $\lbrace b_{t,i} \rbrace$，输出 $\lbrace b_{x_t,i} \rbrace$；如果找不到，直接输出 $\lbrace a_i \rbrace$。时间复杂度 $\mathcal{O}(n^2 + qn)$；但只要及时 break; 就可以通过了，跑得还很快。好像目前为止其他题解都是这个做法？

继续优化上面的做法，发现上一做法的瓶颈为暴力向后找首个替换。我们可以维护 $k$ 个序列，第 $i$ 个序列降序维护 $p_t=i$ 的所有 $t$。仍然倒序枚举 $t$，对于每个 $t$ 遍历所有 $1 \le i \le k$，在上文所述的 $k$ 个序列中找到每个 $i$ 第一次替换的位置，取最小值即可。这样对于每个序列就需要维护“追加一个数”和“找到最后一个大于某数的数”，不难想到单调栈上二分实现。代码大概长这样：

// 当前需要找到 a[k] 第一次被替换的位置，b[n][k] 是操作序列，v[k] 是 k 个单调栈，用 vector 实现
inline int ask(int *a){
    int pos=n+1;
    for(int i=1;i<=k;i++){ // 遍历每个位置
        int l=0,r=v[i].size();
        while(l<r){
            const int mid=(l+r)>>1;
            b[v[i][mid]][i]<=a[i]?r=mid:l=mid+1;
        } // 二分找到第一个小于等于某数的数的位置 l，l-1 就是最后一个大于该数的数
        if(l)pos=min(pos,v[i][l-1]); // 取所有结果的最小值
    }
    return pos;
}

// 对 t=i 维护单调栈，栈顶到栈底严格递增
while(v[p[i]].size() && b[v[p[i]].back()][p[i]]<=b[i][p[i]])
        v[p[i]].pop_back();
v[p[i]].emplace_back(i);

询问时同理。总时间复杂度 $\mathcal{O}((n+q)k \log n)$；但上一做法根本卡不满，所以两者的实际表现并没有很大差别。提交记录