## 数据范围与约定

$1$ $5$ $5$
$2$ $10$ $10$
$3$ $15$ $15$
$4$ $100$ $100$
$5$ $100000$ $100$
$6$ $100000$ $100$
$7$ $100000$ $100$
$8$ $100000$ $100000$
$9$ $10^7$ $10^7$
$10$ $10^7$ $10^7$

## 分析

### 70pts

$70$ 分的做法是一个比较直观的 $\text{dp}$。

• 若第 $i$ 个桶没有放球，则有 $f[i - 1][j]$ 种方案。
• 若第 $i$ 个桶放了球，则先考虑前 $i - 1$ 个桶的状况，一共有 $f[i - 1][j - 1]$ 种不同的方案，而第 $i$ 个桶放的球必须在剩下的 $(2i - 1) - (j - 1) = 2i - j$ 个球中选择，则共有 $(2i - j) \times f[i - 1][j - 1]$ 种不同的方案。

### 100pts

$10^7$ 的数据范围与 $10^5$ 的询问次数已经明确表示标算一定是 $O(T \log n)$ 或 $O(T)$ 的。