给定一个序列 \(A\),求出:
\[\sum \limits_{i=1}^N \sum \limits_{j=i+1}^N \max(A_j-A_i,0) \]答案小于 \(2^{63}\)。
思路
这里提供三种思路(分块经 XXR 尝试,卡常卡不过):
1 权值树状数组
将 \(A\) 离散化,设 \(rk_i\) 为 \(A_i\) 离散化后的排名,去重后元素个数为 \(M\)。
每个结点维护两个值:区间和、区间元素个数。
倒序遍历 \(A\),遇到 \(A_i\) 时,先将答案加上 \(rk_{A_i}+1 \sim M\) 区间的区间和,然后减去区间元素个数 \(\times A_i\)。接着将 \(rk_{A_i}\) 结点的区间和加上 \(A_i\),区间元素个数加上 \(1\)。
可以发现,操作为单点修改、区间查询,可以用树状数组。
时间复杂度为 \(\mathcal{O}(N \log N)\)。
2 权值线段树
既然有树状数组,那么就有线段树。
时间复杂度为 \(\mathcal{O}(N \log N)\)。
3 平衡树
可以用 FHQ_Treap。每个结点维护子树和子树大小。
倒序遍历 \(A\),遇到 \(A_i\) 时,将平衡树分裂为两棵树,\(x\) 存小于等于 \(A_i\) 的结点,\(y\) 存大于等于 \(A_i\) 的结点。让答案加上 \(y\) 子树的子树和,然后减去子树大小 \(\times A_i\)。接着将 \(A_i\) 插入平衡树,并合并 \(x,y\)。
分裂和合并的时间复杂度为 \(\mathcal{O}(\log N)\),因此时间复杂度为 \(\mathcal{O}(N \log N)\)。
标签:AtCoder,结点,log,复杂度,abc351,讲解,区间,mathcal,rk From: https://www.cnblogs.com/lrxmg139/p/18164491