2023.8.7 闲话

题意：给定一个 $n$ 的排列 $a_i$，定义 $f(l,r,x)$ 表示区间 $[l,r]$ 中小于 $x$ 的数的个数。对于每个 $i\in [1,n]$，求出

$\displaystyle \sum_{l=1}^i\sum_{r=i}^n f(l,r,a_i)$

$n\leq 2\times 10^5$。

题解：前两天刚讲过二维数点，今天就用上了。

对于每个 $i$ 拆一下贡献。

• 满足 $j<i$ 且 $a_j<a_i$ 的 $j$ 能对 $i$ 的答案产生 $j\times(n-i+1)$ 的贡献。
• 满足 $j>i$ 且 $a_j<a_i$ 的 $j$ 能对 $i$ 的答案产生 $i\times(n-j+1)$ 的贡献。

现在有了一个 $\mathcal{O}(n^2)$ 的暴力。

对所有贡献整体考虑，接着拆式子。

• 所有满足 $j<i$ 且 $a_j<a_i$ 的 $j$ 能对 $i$ 的答案一共产生 $(n-i+1)\times\sum j$ 的贡献。
• 所有满足 $j>i$ 且 $a_j<a_i$ 的 $j$ 能对 $i$ 的答案一共产生 $x\times i(n+1)-i\times\sum j$ 的贡献。这里的 $x$ 表示满足条件的 $j$ 的个数。

我们把 $(i,a_i)$ 看作二维平面上的一个点，第一种贡献只需要求左下角为 $(1,1)$ 右上角为 $(i-1,a_i-1)$ 的矩形中 $j$ 的总和，第二种贡献就是在求左下角为 $(i+1,1)$ 右上角为 $(n,a_i-1)$ 的矩形中 $j$ 的总和以及点的个数。

用两个树状数组做二维数点，扫到 $(i,a_i)$ 时在一个上加 $i$ 另一个上加 $1$，套式子就可以求了。

时间复杂度 $\mathcal{O}(n\log n)$。