中考？
不做评价。
Question 1
【AGC023E】
给定一个长度为 \(n\) 的正整数序列 \(A\)，对于一个长度为 \(n\) 的全排列 \(P\)，记 \(I(P)\) 表示 \(P\) 的逆序对数量，求：
\[\underset{\forall 1\leq i\leq n, P_i\leq A_i}{\sum} I(P) \]\(1\leq n\leq 2\times 10^5, 1\leq A_i\leq n\)
满足条件的 \(P\) 的数量
将 \(A\) 升序排列为 \(B\)，假设考虑到第 \(i\) 个位置，上限为 \(B_i\)，有 \((B_i - (i-1))\) 个合法位置，故总方案数为：
\[T = \overset{n}{\underset{i=1}{\prod}} (B_i - i + 1) \]记 \(f_i = B_i - i + 1\)。
\(I(P)\) 的相关推导
考虑每一对满足 \(1\leq i < j\leq n\) 的 \((i,j)\) 的贡献 \(g(i,j)\)，即 \(T\) 个方案中满足 \(P_i > P_j\) 的方案数量，讨论：
若 \(A_i < A_j\)
由于 \(P_i > P_j\)，所以将 \(A_j\) 直接视为 \(A_i\) 没有任何影响。
顺序考虑每一个 \(B_i\)，记 \(c_i\) 表示原 \(A_i\) 的排名。
\((P_i,P_j)\) 有 \(\binom{f_i}{2}\) 种方案数，然后其余的 \(P_x\) 的方案数为 \(\dfrac{T}{f_if_j}\)，当然，如果 \(P_j\) 在 \([1,B_i]\) 内取值，对于满足 \(c_i < c_k < c_j\) 的 \(k\)，其选择数量少了 \(1\)（不能取 \(P_j\)），所以：
\[g(i,j) = \dfrac{T(f_i-1)}{2f_j} \underset{c_i < c_k < c_j}{\prod} \dfrac{f_k-1}{f_k} \]扫描 \(j\)，我们需要一次性求出 \(\underset{i<j}{\sum} g(i,j) = \dfrac{T}{2f_j} \underset{i< j}{\sum} (f_i-1)\underset{c_i < c_k < c_j}{\prod} \dfrac{f_k-1}{f_k}\)。
于是考虑 \(h(i,j) = (f_i-1)\underset{c_i < c_k < c_j}{\prod} \dfrac{f_k-1}{f_k}\)，固定 \(i\)，当 \(j\gets j+1\) 时，有 \(h(i,j+1) = h_{i,j}\times \dfrac{f_j-1}{f_j}\)。
上线段树维护即可。
若 \(A_j < A_i\)
考虑逆序对会g，所以考虑顺序对，将上面 \(i,j\) 倒置即可，而方案数需要用 \(T\) 减去该种情况的方案数。
相当于这里的方案数的系数是 \(-1\)，统一放在线段树里维护，由于还有多个 \(T\) 要加上，用一个树状数组维护满足 \(i<j, A_i > A_j\) 的相关数据。
最终时间复杂度为 \(\mathcal{O}(n\log_2 n)\)。
标签：方案,underset,2024.6,23,dfrac,unkown,leq,考虑,prod From： https://www.cnblogs.com/ydzr00000/p/18263229