不难发现原题等价于给定序列前缀查询。

请问改成区间查询有什么比较阳间的做法吗。。qwq