tkdsheep-solution-0024
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
这是KT学姐的第一道神题，这次集训学姐一共出了4题，每道都是比较厉害的数据结构优化题
作为验题的苦逼表示痛并快乐着。。无限仰慕。。做完之后还是挺有收获的
所以后面我和组里的小龙龙童鞋又合力出了一道蘑菇题0042，需要用到这题的单调队列思想，不过0042那题的数据似乎弱了一点，我会对题库的数据进行加强的
回过头来，这题的大意就是给n个积木，每个积木有一个高度h和一个坐标x，现在我可以推倒任意的一片积木，推的时候要选定方向，只能向左或者向右
积木推倒后，凡是在选定方向上与这个积木的距离小于等于h的其他积木都会被推倒，并且产生连锁反应（类似多米诺骨牌）
举个例子，n个积木
x坐标分别为1,2,3,4,5,6,
高度分别为1,2,3,4,5,1
如果我往左推第六块积木，它的高度是1，只能碰到第五块积木，第五块积木跟着往左倒下，产生连锁反应，由于第五块积木高度为5，所以会把左边的所有积木都压倒
现在题目的问题就是给出每个积木的高度，问最少推几次才能把所有积木推倒
做法肯定是dp，但是这题比较麻烦的一个地方是它有两个方向可以推倒，所以可能有那种“包饺子”的推法，即两边往中间倒
标程似乎是分左和右两种情况来分别dp的，我是直接一个dp数组来做
dp[i]表示前i个积木，不管我用什么方法，向左向右都可以，最少要几次才能推倒
则大类有两种情况
1. 把i往左推倒，则用dp[j]+1更新dp[i]，这里j要保证i往左倒能够碰到第j+1个木块，即left[i]-1是边界（left[i]表示i往左推，最远能推倒到第几个积木）
所以相当于在left[i]-1到i-1这个区间上找一个最大的dp值来更新dp[i]，这个可以用线段树来查询区间最值，复杂度为logn
2. i是前面的某个积木向右推，顺带把i碰倒的，则我们在前面找所有往右推能碰到i的积木j（即right[j]>=i），用dp[j-1]+1去更新i
第2步实际上不用往前枚举，每次dp[j]计算完，就塞到一个优先队列里，当更新dp[i]的时候，从优先队列里pop出【次数最少】的dp值
假设pop出来的是dp[j]，那么就看j+1这个积木能不能推到i，不能的话就直接扔掉dp[j]，因为i+1更不可能被j+1推得到了
继续从队列里pop其它的dp值直到队列为空或者找到能推到i的dp[j]值，用dp[j]+1更新dp[i]，然后就不用再更新了，因为优先队列里剩下的dp值次数只会更高
每个dp值进队1次，出队1次，均摊下来每次更新的复杂度都是logn
综上，dp的复杂度是nlogn的，用了线段树+优先队列
此外。。这题在预处理的时候还需要用单调队列优化。。不然还是会超时。。orz
预处理什么？当然是每个积木往左和往右推最远能推到哪里~
这个单调队列的优化我暂时先不写，如果你看懂了上面的优先队列优化的思路，那么这个单调队列是不难想的~有疑问可以留言评论
此外~这题出数据的时候出现了失误，有些木块的X坐标是一样的@.@汗。。所以比赛的时候我加了个条件，就是如果X坐标相同，无论你推哪个积木，这些坐标相同的都会同时朝相同方向倒下
所以贪心的肯定推最高的那块，于是把x坐标相同的积木合并成最高的那一块即可
}}}这是KT学姐的第一道神题，这次集训学姐一共出了4题，每道都是比较厉害的数据结构优化题
作为验题的苦逼表示痛并快乐着。。无限仰慕。。做完之后还是挺有收获的
所以后面我和组里的小龙龙童鞋又合力出了一道蘑菇题0042，需要用到这题的单调队列思想，不过0042那题的数据似乎弱了一点，我会对题库的数据进行加强的
回过头来，这题的大意就是给n个积木，每个积木有一个高度h和一个坐标x，现在我可以推倒任意的一片积木，推的时候要选定方向，只能向左或者向右
积木推倒后，凡是在选定方向上与这个积木的距离小于等于h的其他积木都会被推倒，并且产生连锁反应（类似多米诺骨牌）
举个例子，n个积木
x坐标分别为1,2,3,4,5,6,
高度分别为1,2,3,4,5,1
如果我往左推第六块积木，它的高度是1，只能碰到第五块积木，第五块积木跟着往左倒下，产生连锁反应，由于第五块积木高度为5，所以会把左边的所有积木都压倒
现在题目的问题就是给出每个积木的高度，问最少推几次才能把所有积木推倒
做法肯定是dp，但是这题比较麻烦的一个地方是它有两个方向可以推倒，所以可能有那种“包饺子”的推法，即两边往中间倒
标程似乎是分左和右两种情况来分别dp的，我是直接一个dp数组来做
dp[i]表示前i个积木，不管我用什么方法，向左向右都可以，最少要几次才能推倒
则大类有两种情况
1. 把i往左推倒，则用dp[j]+1更新dp[i]，这里j要保证i往左倒能够碰到第j+1个木块，即left[i]-1是边界（left[i]表示i往左推，最远能推倒到第几个积木）
所以相当于在left[i]-1到i-1这个区间上找一个最大的dp值来更新dp[i]，这个可以用线段树来查询区间最值，复杂度为logn
2. i是前面的某个积木向右推，顺带把i碰倒的，则我们在前面找所有往右推能碰到i的积木j（即right[j]>=i），用dp[j-1]+1去更新i
第2步实际上不用往前枚举，每次dp[j]计算完，就塞到一个优先队列里，当更新dp[i]的时候，从优先队列里pop出【次数最少】的dp值
假设pop出来的是dp[j]，那么就看j+1这个积木能不能推到i，不能的话就直接扔掉dp[j]，因为i+1更不可能被j+1推得到了
继续从队列里pop其它的dp值直到队列为空或者找到能推到i的dp[j]值，用dp[j]+1更新dp[i]，然后就不用再更新了，因为优先队列里剩下的dp值次数只会更高
每个dp值进队1次，出队1次，均摊下来每次更新的复杂度都是logn
综上，dp的复杂度是nlogn的，用了线段树+优先队列
此外。。这题在预处理的时候还需要用单调队列优化。。不然还是会超时。。orz
预处理什么？当然是每个积木往左和往右推最远能推到哪里~
这个单调队列的优化我暂时先不写，如果你看懂了上面的优先队列优化的思路，那么这个单调队列是不难想的~有疑问可以留言评论
此外~这题出数据的时候出现了失误，有些木块的X坐标是一样的@.@汗。。所以比赛的时候我加了个条件，就是如果X坐标相同，无论你推哪个积木，这些坐标相同的都会同时朝相同方向倒下
所以贪心的肯定推最高的那块，于是把x坐标相同的积木合并成最高的那一块即可