使用前缀和优化询问即可。

其实很简单的

测试点强度太高了，看不懂啊

看到好多说测试点错了，反正我是AC了。