为了方便表示，我将以 xxx 开头，yyy 结尾的子串数量称为 {x,y}\{x,y\}{x,y}，数组 aaa 中大于数 xxx 的个数称为 a.LB(x)a.LB(x)a.LB(x).
个人认为本次巅峰赛最难的一题！
认真读题，可发现题目实际让我们找的是如下的代码：
首先，我想到两个块合并只需要把左右两个块的 {x,y}\{x,y\}{x,y} 相加再加上第一个块内 xxx 的数量乘第二个块内 yyy 的数量即可.
于是我轻松地打了个线段树代码：
然后内存爆了.
后来我尝试用分块做，TLE了.
最后我使劲想想想，终于想出来了：
我们不需要维护整个线段树，真正需要维护的只是 676676676 个结果.
我们可以换个角度考虑，如aababbaababbaababb，将第 555 个字符改成 aaa：
先统计负贡献：
1. 在前四个字符与第五个字符的关系中，{a,b}−=3\{a,b\}-=3{a,b}−=3，{b,b}−=1\{b,b\}-=1{b,b}−=1.
2. 在第六个字符与第五个字符的关系中，{b,b}−=1\{b,b\}-=1{b,b}−=1.
再统计正贡献：
1. 在前四个字符与第五个字符的关系中，{a,a}+=3\{a,a\}+=3{a,a}+=3，{b,a}+=1\{b,a\}+=1{b,a}+=1.
2. 在第六个字符与第五个字符的关系中，{a,b}+=1\{a,b\}+=1{a,b}+=1.
我们发现，如果把这个字符串拆开，分为 aaa 字符串与 bbb 字符串：
那么贡献就与 555 在 aaa 字符串与 bbb 字符串的相对位置，即 ∑i∈ba.LB(i)\sum\limits_{i\in b} a.LB(i)i∈b∑ a.LB(i) 有关.
其它的字符串也有这个性质，自行验证.
可以亮代码了……吗？
等等，还有两件事没讲清楚.
1.如何快速求 a.LB(x)a.LB(x)a.LB(x):
如果按正常的数组处理的话，修改时间复杂度就得退化至 O(n)O(n)O(n)；
而 setsetset 只会给你返回迭代器，转换成数值又得花费 O(n)O(n)O(n) 的时间.
怎么办呢？
机智的我想到了用树状数组模拟数组！只要每次加入元素在该元素的下标增加 111，删除元素在该元素的下标增加 −1-1−1，那么查询某个下标的结果就是 a.LB(x)a.LB(x)a.LB(x)！
使用这种方法也可以以 O(nlogn)O(n\log n)O(nlogn) 的时间复杂度求得一个数组的逆序对.
2.初始化时间复杂度问题：
确实，通过上面的办法可以让修改变为 O(logn)O(\log n)O(logn)，查询变为 O(1)O(1)O(1)，但是要初始化. 而如果按照上面的代码初始化，时间复杂度是 O(n2)O(n^2)O(n2)！
没关系，稍微推导一下，就可以推出 {x,y}=∑i∈yx.LB(i)+(i∈x)\{x,y\}=\sum\limits_{i\in y} x.LB(i)+(i\in x){x,y}=i∈y∑ x.LB(i)+(i∈x).
该题代码如下：
