题解：Lazy Sort

问题分析

本题可通过分析懒牛排序的本质，结合组合数学和动态规划求解。关键观察如下：

1. 懒牛排序过程：每头牛会将箱子传递给身后的牛，直到数组非递减。最终数组 ( B ) 满足：

   • ( B ) 是非递减数组
   • ( B ) 与原数组 ( A ) 的前缀和相等（箱子总数守恒）
   • 题目要求 ( B ) 是 ( A ) 的升序排列

2. 核心约束：设 ( A ) 的升序排列为 ( S )，则 ( S ) 必须是非递减且与 ( A ) 前缀和相同。通过分段处理已知值区间，可将问题转化为计算每段满足约束的序列数量。

算法思路

1. 分段处理：按已知值位置将数组分为 ( Q-1 ) 段，每段需满足：

   • 首尾值固定（由已知值或前一段约束确定）
   • 段内元素需满足非递减关系
   • 段内前缀和需符合总约束

2. 动态规划状态：用 ( f[cl] ) 表示当前段结束时，状态为 ( cl )（0 或 1）的方案数，其中 ( cl ) 用于跟踪边界条件。

3. 组合计数：对每段计算合法序列数，利用：

   • 阶乘和逆元预处理组合数
   • 隔板法计算满足多重约束的序列数量
   • 快速幂处理 ( 2^k ) 形式的项（模 ( 10^9+7 )）

复杂度分析

• 时间复杂度：( O(N + Q \cdot L \cdot 2^2) )，其中 ( L ) 为分段的最大长度。预处理阶乘和逆元需 ( O(N) )，分段处理中每段的组合数计算为 ( O(L) )。
• 空间复杂度：( O(N) )，用于存储阶乘、逆元等预处理数组。

该算法通过分段动态规划和组合数学计数，高效解决了大范围内的约束计数问题，符合题目对 ( N \leq 5 \times 10^6 ) 的要求。