这道题要求我们找出一个排列中，有多少个连续子区间 的逆序对数量恰好等于 。
直接去求“恰好等于”某个值的区间个数不太好直接搞，所以这份代码使用了一个非常经典的差分套路。
思路大概是这样的：
我们要找“恰好等于 ”的数量，其实就等于“逆序对数 的数量”减去“逆序对数 的数量”。
所以在代码的主函数里，最终的答案就是 calc(k) - calc(k-1)。这样一来，问题的核心就转化成了：如何求逆序对数量 （某个指定上限）的区间总数。
为了求出满足条件的区间数，代码使用了双指针（滑动窗口）配合权值线段树来实现。
我们可以维护一个动态的窗口，左端点是 ，右端点是 。我们让 从 到 遍历整个数组。
每当 往右走一步，窗口里就多了一个新数字 （代码里的 ）。这个新数字会和窗口里原有的数字产生新的逆序对。具体产生多少个呢？因为 是当前窗口最右边的元素，所以它和前面的元素构成的逆序对数量，就是当前窗口里比 大的数字的个数。
我们在代码里用 query(1, 1, n, a[r]+1, n) 查出了这个数量，并加到当前的逆序对总数 里，然后把 放进线段树 add(1, 1, n, a[r], 1)。
但是，加入新数字后，窗口里的逆序对总数 可能会超过我们允许的上限 。这时候我们就只能让左指针 往右走，把最左边的数字 踢出窗口，直到 为止。
当 离开窗口时，它原本和窗口里其他数字构成的逆序对也会消失。它和谁构成了逆序对呢？因为它是窗口最左边的数字，所以排在它右边且比它小的数字，都会和它构成逆序对。
我们用 query(1, 1, n, 1, a[l]-1) 查出窗口里比 小的数字个数，从 里面减去，然后把 从线段树里删掉 add(1, 1, n, a[l], 0)，最后 。
当内部的 while 循环结束时，我们就得到了一个以 为结尾的、满足逆序对数量 的最长区间 。
既然最长的区间符合条件，那么它内部所有以 结尾的更短的区间（也就是 ）肯定也都符合条件，因为区间越短逆序对只可能越少。这样的合法区间一共有 个。把每一轮计算出的个数累加起来，就得到了函数最后的返回值 。
最后简单说一下底层的数据结构。
为了在滑动窗口的过程中，快速求出“当前窗口内大于/小于某个数的数字有几个”，代码手写了一棵线段树，把它当成了一个值域桶来用。遇到一个数就在对应数值的位置标记为 ，离开窗口就标记回 。利用线段树求区间和，就能在 的时间内查出结果。整个 calc 函数的时间复杂度是 ，跑两次滑动窗口完全没有问题。