首先可以将 与上一个非负的位置做差，得到这一段咖啡的数量。我们考虑维护每一段的数量，然后将这些段拼起来。我们记 表示以 开始的段，第一个位置和最后一个位置是否是咖啡的方案数。
我们先考虑从 个位置里选出 个不相邻的位置的方案数。考虑换个角度，不是从 个里面选出 个，而是将 个位置插入到剩下 个位置中间。 个位置之间有 个空位，因此答案就是 。
假如我们要钦定开头的位置必须是茶壶，那么就是剩下 个空隙里选择 个，答案就是 。剩下的几种情况也类似。 将两段拼起来的方法是简单的，只需要枚举头尾是否是咖啡，中间不要让咖啡拼到一起即可。假设我们要用 和 拼出 ，以 举例：
接下来我们考虑如何快速将所有这些段拼起来。容易想到一个方法，从前往后枚举每一段，暴力转移。这样的询问复杂度最坏是 的（考虑每个 都非负的情况），但是单次修改可以 修改。同时，我们也可以考虑另外一种方法，维护 表示在 之前所有段拼接起来的结果， 表示将 之后的所有段拼接起来的结果。这样我们修改一段之后可以 得到结果，但是每次修改必须要重建 和 ，最坏也是 的。
那么，有没有方法来平衡一下这两种方案，使得修改和查询的复杂度都可以接受呢？显然是有的。我们可以考虑分块。我们对每段的左端点分块，记块长为 。
对于位于第 个块内的，左端点是 的段，记下一个块的第一段左端点为 ，维护 表示 到 这一段的方案数，前和后是否是咖啡。这样在修改某一段的时候只需要重构整个块的答案，最坏是 的。重建时，对于一个块最后的一段， 显然就是这段的方案数，对于其他段，只需要将这段的方案数与下一段的 拼起来即可。询问时只需要从第一个块跳到最后一个块，把每个块第一段的 拼起来就可以得到答案，最坏 。取 平衡复杂度即可做到在 的复杂度下解决这个问题，在常数优秀的情况下可以卡过去。
实现时需要注意，最后一段没有咖啡个数的限制，需要特殊处理。
实际上这个方法本质上就是用分块维护矩阵的乘积，和用其他方法（线段树等）维护矩阵的方法殊途同归。代码在这里。