古法编程日记

Codeforces Round 1096 (Div. 3): E. It All Went Sideways

给定一个长度为 $n$ 的数组 $a$，表示 $n$ 列竖直堆叠的单位立方体，其中 $a_i$ 表示第 $i$ 列的高度，即第 $i$ 列在高度 $1,2,\ldots,a_i$ 各有一个立方体。

现在重力方向从“向下”变为“向右”。每个立方体会在保持原高度不变的情况下，尽可能向右滑动；立方体不能穿过或重叠其他立方体。最终状态由初始数组唯一确定。

在重力改变前，你最多可以执行一次操作：选择一个下标 $i$，使 $a_i$ 减少 $1$，也就是从第 $i$ 列移除一个立方体；也可以不操作。

如果一个立方体在重力改变后所在的列编号与原来的列编号不同，则称它发生了移动。

求重力改变后最多有多少个立方体会发生移动。

分析

定义数组 $\mathrm{sf}$，意为 suffix min，其中

对于一个给定的数组 $a$，我们依次检查每一列立方体。若当前列右侧的所有列高度都大于等于当前列高度，则当前列的所有立方体都不会移动；否则，当前列中会发生移动的立方体数量等于当前列高度与其右侧最小高度之差。则会发生移动的立方体数量为

根据题目，我们可以进行一次“移除”操作。如上图，如果我们移除位置 1 的立方体，不会有更多的立方体被移动，事实上，由于一个本应移动的立方体被移除了，总的发生移动的立方体数量非但没有增加，还减少了；若移除位置 2 的立方体，则被标记为橙色的立方体会被额外移动。

基于上面的观察，我们可以得到以下结论：

• 若被移除的立方体右侧存在高度更低的列，即 $a_i > \mathrm{sf}_i$，则该立方体本身原本就会发生移动，移除它不会带来额外收益，因此没有必要执行该操作。
• 若移除第 $i$ 列的一个立方体是有收益的，则从第 $i$ 列向左考虑，直到到达数组开头，或遇到第一列高度严格小于 $a_i$ 的列为止。这个过程中经过的列数，恰好等于因本次移除操作而额外发生移动的立方体数量。
• 考虑到 $\mathrm{sf}$ 是单调不减的，若移除第 $i$ 列的一个立方体能够带来收益，则该收益可以表示为 $i - j - 1$, 其中 $j$ 是满足 $j < i$ 且 $\mathrm{sf}_j < \mathrm{sf}_i$ 的最大下标。换言之，$j$ 是第 $i$ 列左侧距离其最近、且后缀最小值严格小于 $\mathrm{sf}_i$ 的位置。若不存在这样的 $j$，即被移除立方体左侧直到数组边界的所有立方体都会移动，此时收益为 $i-1$。

由此，可得到一个复杂度为 $\mathcal{O}(n)$ 的算法。

using i64 = long long;
 
i64 gravity(const std::vector<i64> & arr , const std::vector<i64> & suffix_min ){
    auto values = 
    std::views::iota((i64)0, static_cast<i64>(arr.size()))
    | std::views::transform(
        [&](i64 i){return std::max((i64)0 , arr[i] - suffix_min[i]);}
    );
    return std::accumulate(values.begin() , values.end() , (i64)0);
}
 
void solve(){
    int n ; std::cin >> n ;
    std::vector<i64> arr(n); for(auto & elem : arr) std::cin >> elem;
    std::vector<i64> suffix_min(arr.size()) , benifit(arr.size() , 0);
    suffix_min.back() = arr.back();
    for (auto i : std::views::iota(0, static_cast<int>(suffix_min.size()-1)) | std::views::reverse )
        suffix_min[i] = std::min(suffix_min[i + 1], arr[i]);
    
    for(auto i :  std::views::iota(1 , static_cast<int>(benifit.size())))
        if(suffix_min[i] == suffix_min[i-1]) benifit[i] = benifit[i-1] + 1 ; 
        
    std::println("{}",gravity(arr, suffix_min) + *std::max_element(benifit.begin() , benifit.end()));
}

Educational Codeforces Round 190 (Rated for Div. 2): D. Good Schedule

Alice 和 Bob 看电视剧，但他们选择的电视台会以不同的顺序来播放电视剧。两个电视台每天都只播一集，具体播放的集数用一个数组表示。

举例来说，若 Alice 选择的电视台所对应的数组为 $[a,b,c]$ , 意为第一天播放第 $a$ 集，第二天播放第 $b$ 集，第三天播放第 $c$ 集。

Alice 和 Bob 的行为模式是一致的，如果电视台选择播放第 $i$ 集，他们只会在自己已经看过前 $i-1$ 集（即第 $1,2,3,\dots,i-1$ 集）的时候才会观看这一集。否则，即便播放了某集，他们也不会看。

Alice 和 Bob 期望找到一个时间段 $[L,R]$ ，在这段时间内，他们每天的进度都是一致的。

问能找到多少个这样的时间段 $[L,R]$ ( $1\leq L \leq R \leq n , n \leq 5 \cdot 10^5$ )

分析

由于 Alice 和 Bob 行为模式一致，且我们期望两人进度相同，故不区分二者。将两个电视台在同一天播放的剧集编号视为一个无序对，记为 $\{x, y\}$（其中 $x, y$ 为正整数，表示第几集）。例如 $\{1, 1\}$ 表示两个台都播放第 1 集，$\{1, 2\}$ 表示一台放第 1 集、另一台放第 2 集。 由题可观察到以下性质：

• 若某天所对应的无序对为 $\{1, a\}$ 且 $a \neq 1$，则不可能从这一天开始。因为这会造成两人的进度不一致。其他的情况下，都可以从这一天开始。特别的，如果无序对为 $\{1,1\}$，则两人的进度为 $1$，其它情况下两人的进度为 $0$。
• 选定 $L$ 之后，开始观看剧集，假设目前两人的进度为 $p$，则遇到 $\{p+1 , a\} (a \neq p+1)$ 的时候不能继续。若遇到 $\{p+1,p+1\}$ ，则进度可以更新为 $p+1$ 。
• 若区间 $[L, R]$ 合法，则对所有整数 $r = L, L+1, \dots, R$，区间 $[L, r]$ 也合法。

一个初步的想法是，对于每个 $L$ ，用最快的速度找到最靠右的 $R$ 即可。最好能在 $\mathcal{O}(\log n)$ 的时间内完成这件事。这样的话，总体的复杂度为 $\mathcal{O}(n \log n)$。假设有一函数 $f(L) = bestR$，我们的任务转化为找到这个函数的计算方法。