考虑使用颜色段均摊技巧维护序列，然后对每个权值利用一棵动态开点权值线段树维护该权值在序列中的出现位置。对于查询操作，贪心地尽量靠左匹配原序列，维护当前匹配到的位置，对给定的每个段在对应的动态开点权值线段树上二分得到匹配完成时的位置即可。

最终的时间复杂度为 $O(n \log n + m \log n + q \log n)$，空间复杂度为 $O(n \log n + q \log n)$。

（用平衡树存储每个权值对应的颜色段来代替动态开点权值线段树，可以将空间复杂度优化到 $O(n + q)$，但可能会影响程序运行性能并增加代码编写难度。）