• POJ 1990 MooFest 树状数组


    一、题目大意

    我们有N头牛,需要两两之间相互通讯,其中每头牛对应一个坐标x和一个听力v,设第i头牛的听力为v(i),坐标为x(i)(1<=x<=20000),

    已知牛i和牛j相互通讯需要的音量为 max(v(i),v(j))*|x(i)-x(j)|,求出N(N-1)对通讯的音量的总和。

    二、解题思路

    我们首先看下,牛i和牛j相互通讯需要的音量为 max(v(i),v(j))*|x(i)-x(j)|,那么如果我们对所有的牛根据v来排序,保证对于 i < j ,v[i] <= v[j],之后从第一个开始循环,计算 i 和 i 前面的所有牛的坐标差之和  * v[i]即可。 

    然后我们可以记录2个树状数组,其中一个bit用来存坐标,另一个用bitCnt来计数,每一次循环执行如下的事情

    1)计算bit的前 x[i]项和leftSum,和 前 262144 的和allSum(所有元素)

    2)计算bitCnt前 x[i]项和leftCnt,和 前 262144 的和allCnt(所有个数)

    3)其中leftCnt就是牛i左边的牛的坐标和,例如3头牛 1 2 5,那么它左边的坐标和为1+2=3,然后leftCnt就是牛i左边牛的数量,即2,那么 i 和左边的坐标差=(5-1)+(5-1)=5 * 2 - (2 + 1)

    所以左边的牛的音量 = (x[i] * leftCnt -  leftSum )*v[i]

    然后allCnt-leftCnt就是右边的数量rightCnt,allSum-leftSum就是右边的数量rightSum

    同理右边的牛的音量 = ( rightSum - x[i]*rightCnt )*v[i]

    之后把左右两边音量的和加到ans里即可

    4)将bit的x[i]位+x[i],将bitCnt的x[i]位+1

    bit[ x[ i ] ]+=x[i]

    bitCnt[ x[ i ] ]+=1

    同步更新两棵树的父节点...

    (备注:本题目中坐标乘以数量然后不断求和的过程中 n * (n-1) * 20000可能会大于int32,注意给结果开long long)

    三、代码

    1. #include
    2. #include
    3. using namespace std;
    4. typedef long long ll;
    5. typedef pair<int, int> P;
    6. P num[262150];
    7. int bit[262150], n_, n, bitCnt[262150];
    8. ll ans = 0LL;
    9. void input()
    10. {
    11. scanf("%d", &n_);
    12. for (int i = 1; i <= n_; i++)
    13. {
    14. scanf("%d%d", &num[i].first, &num[i].second);
    15. }
    16. sort(num + 1, num + (1 + n_));
    17. }
    18. void init()
    19. {
    20. n = 262144;
    21. for (int i = 0; i <= n; i++)
    22. {
    23. bit[i] = 0;
    24. bitCnt[i] = 0;
    25. }
    26. }
    27. void update(int r, int v)
    28. {
    29. if (r <= 0)
    30. {
    31. return;
    32. }
    33. for (int i = r; i <= n; i = i + (i & (-i)))
    34. {
    35. bit[i] = bit[i] + v;
    36. }
    37. }
    38. void updateCnt(int r, int v)
    39. {
    40. if (r <= 0)
    41. {
    42. return;
    43. }
    44. for (int i = r; i <= n; i = i + (i & (-i)))
    45. {
    46. bitCnt[i] = bitCnt[i] + v;
    47. }
    48. }
    49. int query(int r)
    50. {
    51. int sum = 0;
    52. for (int i = r; i > 0; i = i - (i & (-i)))
    53. {
    54. sum = sum + bit[i];
    55. }
    56. return sum;
    57. }
    58. int queryCnt(int r)
    59. {
    60. int sum = 0;
    61. for (int i = r; i > 0; i = i - (i & (-i)))
    62. {
    63. sum = sum + bitCnt[i];
    64. }
    65. return sum;
    66. }
    67. void solve()
    68. {
    69. for (int i = 1; i <= n_; i++)
    70. {
    71. int leftSum = query(num[i].second);
    72. int allSum = query(n);
    73. int leftCnt = queryCnt(num[i].second);
    74. int allCnt = queryCnt(n);
    75. ans = ans + (((ll)((leftCnt * num[i].second) - leftSum)) * ((ll)num[i].first));
    76. ans = ans + (((ll)((allSum - leftSum) - ((allCnt - leftCnt) * num[i].second))) * ((ll)num[i].first));
    77. update(num[i].second, num[i].second);
    78. updateCnt(num[i].second, 1);
    79. }
    80. }
    81. int main()
    82. {
    83. input();
    84. init();
    85. solve();
    86. printf("%lld\n", ans);
    87. return 0;
    88. }

  • 相关阅读:
    什么是Redis脑裂,如何解决呢
    Python pywin32实现word和Excel的处理
    协议(网络协议)
    探索性测试: 工具和方法的综合应用
    新加坡星银行项目组笔试题面试题
    卷积神经网络中的卷积核,卷积神经网络大小计算
    华为OD机试 - 垃圾信息拦截(Java 2024 C卷 100分)
    K8s配置集群自动LoadBalancer以及IstioGateWay
    内存泄露分析
    Node.js | MongoDB 入门讲解 & Mongoose 模块的初步应用
  • 原文地址:https://blog.csdn.net/qq_53038151/article/details/133498331