T4牛半仙的妹子序列 原博客食用效果更佳 题解 场上被卡常了，下来加了几个优化就卡过去了。 这道题应该很容易看出是一个dp，40pts的的dp式子应该是很好想的。我们定义为在只关注第个数到第个数之间的序列构成合法序列的方案数。容易得到方程式 。 而答案就是我们的。 这种方式的dp是明显可以进行优化的，我们先考虑对那些值产生了贡献。容易发现，产生贡献的满足条件。而这个条件我们需要想办法对其进行维护。对于这个我们可以先按权值建一棵FHQ_Treap，每次进行操作时将值在中的树给裂出去，在那棵值域小于的数加上。 但我们如何保证后半段条件呢？ 我们可以对Treap上的每个点加上一个的值，表示号节点的坐...