本题题解区虽然使用的数据结构不同，但主体的思路是一样的。

但是，本题并非只有一种做法，还有一种非常套路且好想的 $O(nlogn)$ 解法——线段树维护矩阵乘法。虽然常数大了点，但也能通过，并且是一种套路。

写了一篇题解，希望能够通过，若有不合理之处敬请指出。

我的题解