题解：P10300 [THUWC 2020] 工资分配

· · 题解

题目传送门

题意简述：给定一个长为 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)；但上一做法根本卡不满，所以两者的实际表现并没有很大差别。提交记录