你好，同学。很高兴能带你一起攻克这道经典的 双指针（滑动窗口） 题目。这道题在 NOI 普及组中属于高频考点，它能很好地训练你对“单调性”的理解以及对“贡献法”计数技巧的掌握。

不要急着写代码，先跟我一起理清思路。

一、 预备知识点

1. 子数组（Subarray）定义：数组中连续的一个或多个元素。
2. 滑动窗口（双指针）：利用区间单调性，通过左右指针的移动，在 $O(N)$ 时间内处理区间问题的技巧。
3. 乘法性质：在元素均为正整数的情况下，区间越长，乘积一定不会变小（具有单调性）。
4. 贡献法计数：统计以某个位置为终点的合法子数组个数，累加得到总数。

二、 题目描述 (NOI 竞赛风格)

题目名称：乘积小于 K 的子数组 (Subarray Product Less Than K)

【问题描述】 给定一个正整数数组 nums 和一个整数 k。 你需要计算并返回该数组内乘积严格小于 k 的连续子数组的数目。

【输入格式】 第一行包含两个整数 $n$ 和 $k$，分别表示数组长度和目标积。 第二行包含 $n$ 个以空格分隔的正整数，表示数组 nums 的元素。

【输出格式】 输出一个整数，表示符合条件的子数组总数。

【样例 1 输入】

4 100
10 5 2 6

【样例 1 输出】

8

(解释：8个子数组分别是：[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]。注意 [10, 5, 2] 积为 100，不小于 100)

【数据规模与约定】

• $1 \le n \le 3 \times 10^4$
• $1 \le nums[i] \le 1000$
• $0 \le k \le 10^6$

三、 启发式引导：草稿纸上的推理过程

请拿出草稿纸，我们以样例 [10, 5, 2, 6], k=100 为例：

第一步：寻找单调性

思考： 如果一个区间 [L, R] 的乘积已经 $\ge k$ 了，那么向右扩展 [L, R+1] 的乘积会怎样？

• 观察： 因为元素都是正整数，乘积只会变大。这意味着如果 [L, R] 不合法，包含它的更长区间也一定不合法。
• 结论： 这符合滑动窗口的使用条件。

第二步：窗口的滑动过程

我们维护一个窗口 [left, right]，代表当前乘积小于 $k$ 的区间：

1. right 向右移，把新数乘进来。
2. 如果乘积 $\ge k$，说明窗口太“肥”了，left 必须向右移，把左边的数除掉，直到乘积再次 $< k$。

第三步：如何“不重不漏”地计数？

这是本题最容易出错的地方。 核心逻辑： 每次 right 移动到一个新位置后，有多少个以 right 结尾的合法子数组？

• 假设当前合法窗口是 [left, right]，那么以 right 结尾的合法子数组有：
  • [nums[right]]
  • [nums[right-1], nums[right]]
  • ...
  • [nums[left], ..., nums[right]]
• 结论： 个数恰好是 right - left + 1。把每个 right 位置对应的这个值加起来，就是总数。

第四步：复杂度分析

• 时间复杂度：虽然有嵌套循环，但 left 指针和 right 指针都只向右移动，不回头。每个元素最多进出窗口一次。复杂度为 $O(N)$。
• 空间复杂度：只需存储原数组，复杂度为 $O(N)$ 或 $O(1)$（如果边读边处理）。

四、 逻辑流程图（算法逻辑提示）

根据上述推理，我们可以画出如下逻辑流程图。请根据此流程图构思你的 C++ 代码。

五、 总结：读题时的关键词

在 NOI 赛场上，看到以下关键词要保持高度警惕：

1. “连续子数组”：通常暗示滑动窗口、前缀和或单调栈。
2. “正整数”：这是一个非常关键的性质，保证了区间的单调性（越长乘积越大）。如果有 0 或负数，滑动窗口将失效，需考虑其他方法（如前缀积+哈希）。
3. “数目/计数”：注意统计方法，是“贡献法”还是直接枚举。
4. “严格小于”：注意边界，当积等于 k 时是不符合条件的。
5. 数据范围：$n=3 \times 10^4$，$O(N^2)$ 的暴力枚举（计算所有区间积）可能会超时（约 $4.5 \times 10^8$ 次运算），$O(N)$ 算法最为稳妥。

教练优化建议：

• 特判：如果 $k=0$ 或 $k=1$，由于数组全是正数，最小乘积也是 1，所以不可能小于 $k$。这种情况一定要在开始时特判，否则在 left 移动的 while 循环中可能会出现逻辑错误。
• 溢出：本题 $k$ 到 $10^6$，但两个数相乘可能很快超过 int。虽然 LeetCode 原题 $k$ 较小，但在 NOI 风格题目中，建议使用 long long 存储“当前积”以防万一。