Lazy Sort

题目描述

农夫约翰有 $N$ 头奶牛（$2 \leq N \leq 5\cdot 10^6$），并试图利用它们的懒惰来把一个长度为 $N$ 的非负整数数组 $A$ 排序。他有很多沉重的箱子，于是让奶牛排成一列，奶牛 $i+1$ 在奶牛 $i$ 的后面，并给第 $i$ 头奶牛 $a_i$ 个箱子（$0\le a_i$）。

奶牛天生很懒，所以它们总想把工作推给别人。从奶牛 $1$ 到 $N-1$ 依次进行，每头奶牛都会看向它后面的那头。如果奶牛 $i$ 的箱子数严格多于奶牛 $i+1$，奶牛 $i$ 认为这“不公平”，并把自己的一个箱子给奶牛 $i+1$。这个过程不断重复，直到每头奶牛都满意为止。

随后，农夫约翰会记录每头奶牛 $i$ 手中持有的箱子数 $b_i$，并用这些值构造数组 $B$。如果 $B = sorted(A)$，那么农夫约翰就会高兴。不幸的是，农夫约翰在数组 $A$ 中只记得 $Q$ 个值（$2 \leq Q \leq \min(N, 100)$）。幸运的是，这些值包括他原本要给第一头和最后一头奶牛的箱子数。农夫约翰记得的每个值以 $c_i \; v_i$ 的形式给出，表示 $a_{c_i}=v_i$（$1 \leq c_i \leq N$, $1\le v_i\le 10^9$）。请计算有多少种不同的方式可以填补缺失的值，使得他会高兴，并对 $10^9+7$ 取模。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $Q$，分别表示奶牛数量和给定信息（查询）数量。

接下来的 $Q$ 行每行包含两个用空格分隔的整数 $c_i \; v_i$，表示奶牛 $c_i$ 初始持有 $v_i$ 个箱子。保证 $c_1 = 1$、$c_Q = N$，且 $c_i < c_{i+1}$（奶牛编号严格递增）。

输出格式

输出一个整数：满足奶牛进行懒惰排序后农夫约翰会高兴的情况下，$a_i$ 的不同赋值方式数量，对 $10^9+7$ 取模。保证至少存在一种合法赋值。

3 2
1 3
3 2

2

6 3
1 1
3 3
6 5

89

提示

在这个例子中，农夫约翰记得数组两端的值。数组 $[3,2,2]$ 和 $[3,3,2]$ 是能让农夫约翰在懒惰排序结束时高兴的合法数组。

SCORING: Inputs 3-4: $N,v_i\le 100$ Inputs 5-6: $N\le 100$ and $v_i \leq 10^6$ Inputs 7-9: $N \leq 2\cdot 10^5$ and $v_i \le 10^6$ Inputs 10-12: $N \leq 2\cdot 10^5$ Inputs 13-15: No additional constraints. Problem credits: Suhas Nagar

标签: USACO|2025|Platinum

来源

USACO|2025|Platinum