分块大法好。

将这个颜色序列分成[tex]n^{\frac{1}{3}}[/tex]个块，每个块[tex]n^{\frac{2}{3}}[/tex]个数，预处理出[tex]ans[i][j][k][/tex](表示块[tex]i\rightarrow j[/tex]中，颜色[tex]1\rightarrow k[/tex]的答案)和[tex]cnt[i][j][k][/tex](表示块[tex]i\rightarrow j[/tex]中，颜色[tex]k[/tex]的个数）。这一步复杂度[tex]O(n^{\frac{5}{3}})[/tex]。

询问的时候，将整个询问区间分成左边、中间整块部分以及右边。中间部分直接用[tex]ans[i][j][k][/tex]求答案，左边和右边的答案可以使用一个个将数插入的方法统计(如果原先个数是[tex]cnt[i][j][k][/tex]，插入后[tex]ans+=2*cnt[i][j][k]+1[/tex]，然后[tex]cnt[i][j][k]++[/tex])。统计完后再把数删掉。复杂度[tex]O(qn^{\frac{2}{3}})[/tex]。

裸的iBWT...[tex]O(n+m)[/tex]时空复杂度（这个m有什么贡献吗@.@)

BWT: 就是题目中的给定一个字符串，求出“矩阵”中的最后一列

iBWT: 给出“矩阵”中的最后一列，求出原串 

可以先算一个[tex]\psi[/tex]变换，然后遍历一遍。详情查阅Wikipedia -- Burrows-Wheeler Transform。