AtCoder Beginner Contest 382 F - Falling Bars

· · 题解

在这里记录我第一次通过 F 题。

题意：给你一个简化版的俄罗斯方块，每一个方块变成一个长条，要求你模拟这些方块掉落后的结果，输出每一个方块的位置的高度。由于题目的特殊，地面高度为 h，最上面的一个高度为 1。

思路：考虑按照方块从低到高处模拟。对于一开始的一个方块都没有放，所有的点都是高度为 h 的。我们放了一个方块，那么这个方块所属区间 [r_i,r_i+c_i-1] 所有位置都将要更新。而一个方块的落脚高度将是这个区间的最低位置，即靠近 1 坐标的位置。设这个落脚高度为 h，那么放完之后，下一个能放的位置将会变成 h-1。那么，我们只需要维护出空格位置即可。我们发现，这个问题可以维护一个能区间赋值，区间取 \min 的线段树，就可以求出答案。当然你也可以直接用扶苏的问题的代码稍加修改。注意初始的高度全部为 h，在维护 tag 时要将 +\infty 的赋值改成 h+1，不要写成 h，不然过不去样例，我是不会告诉你我因为这个吃了一发罚时的。

没有线段树的部分是这样的：

int main(){
    cin>>h>>w>>n;
    for(int i=1;i<=n;i++)cin>>a[i].r>>a[i].c>>a[i].l,a[i].i=i;
    sort(a+1,a+n+1);
    build(1,1,w); // 初始化空格, 最大空格位置位于 h 行, 区间 1...w
    for(int i=1;i<=n;i++){
        lps=a[i].c,rps=a[i].c+a[i].l-1; // 求出 bar 的位置区间
        hgh=qry(1,1,w,lps,rps);   // 查询 lps 到 rps 范围内的最小值, 找到尽可能底下的空格位子 
        upd(1,1,w,lps,rps,hgh-1); // 更改 lps 到 rps 范围内的值, 最大空格位置变为 hgh-1
        ans[a[i].i]=hgh;  // 求出答案, 对于每一个 bar, r'[i] 的值就是 hgh
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<"\n"; // 输出答案
    return 0;
}

总代码有点长，这里放个赛时的链接：代码。