数据结构 - xIao_wU 思维磁场 - Just Run And Never Forget I Have A Dream
TOJ -- 1788. Raising Modulo Numbers
PKU 1990 -- MooFest 树状数组
题目要求在一个横轴上,求出每个点和相对距离 * max( 声音1 , 声音2) ,直接模拟着做的话,复杂度为O(n ^ 2) ,必定超时。
二元集的题目可使用排序来进行有序化操作,由于两个集合的操作是取最大的声音,故可以对v进行升序操作。for(int i=0; i < n; i++)的时候,去声音值为v[i]即可。
而现在主要解决在轴的位置上。对一个点进行操作的时候,可分为坐标前的点和坐标后的点,若坐标前点的个数为 n1 , 总和为 sum1 , 坐标后的点的个数为 n2 , 总和为 sum2 ,则 相对距离和 = (该点的坐标值 * n1) - sum1 + sum2 - (该点坐标值 * n2)。 对坐标总和和位置前后的坐标总数,都可以适用树状数组在O(lgn)的时间来进行动态统计。每次加入点,更新树状数组即可。