比较显然的做法是用bit维护做到 O(nlog−−−√n) O(n\sqrt \log n)。 但是。。作为一名理论计算机科学家傻逼，我们需要 O(nn√) O(n\sqrt n)的做法，注意到如果我们把 (i,ai) (i,a_i)看成点，实际上要求 O(1) O(1)询问一个矩形内点的个数，这个显然可以用可持久化分块来搞，维护每个块内的前缀和和所有块的前缀和——但是空间复杂度是 3nn√ 3