#莫队 #前缀和[[ > [!quote] 题目背景 > > 渴鹅村附近建了一个大商场——Haokee Mall。这个商场非常的大，并且各种商品与店铺数不胜数。好渴鹅十分兴奋，跟你一起跑到了这个大商场里面买东西。 ## 题目描述 商场里面卖 $n$ 件物品，第 $i$ 件物品要 $a_i$ 元才可以购买。不幸的是，好渴鹅今天出门只带了 $k$ 元钱，并且好渴鹅还有强迫症，买的商品的价值之和必须正好为 $k$。 现在好渴鹅给你抛出了 $m$ 个询问，每一个询问都是 $(l,r)$ 的形式。表示好渴鹅如果打算逛 $[l,r]$ 之内的商品，并且连续购买其中的任意部分商品，的价值之和能够正好达到 $k$ 的方案数。 你能够从容地回答出好渴鹅给你的问题吗？ ## 输入格式 - 第一行：$n$ 和 $m$ 两个整数； - 第二行：一共 $n$ 个数，第 $i$ 个数为 $a_i$； - 接下来 $m$ 行：一行一个形如 $(l,r)$ 的询问。 ## 输出格式 - 一共 $m$ 行，表示方案数。 ## 提示说明 | 数据百分比 | $n$ | $m$ | $\max(\sum\limits_{i=1}^na_i,k)$ | | :-----: | :----------------: | :----------------: | :------------------------------: | | $20\%$ | $\le 100$ | $\le 100$ | $\le 1000$ | | $40\%$ | $\le 1000$ | $\le 1000$ | $\le 10^4$ | | $60\%$ | $\le 1000$ | $\le 1000$ | $\le 10^5$ | | $100\%$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^6$ |