• 刷题记录(NC19246 数据结构)


    NC19246 数据结构

    题目链接

    关键点:

    1、如何处理乘法以及计算平方和

    2、首先分析对于区间内每个数+k,对区间平方和的影响:

    ∑(xi+k)² = ∑xi² + 2*k*∑xi + ∑k²

    因此我们只要将该区间的平方和 += 该区间的和*2*k + 该区间长度*k

    tree2[p] += 2*tree1[p]*num + num*num*(r-l+1);

    对于乘k对于区间和、区间平方和影响

    区间和*k = ∑每个元素*k,因此区间和直接乘k即可

    区间平方和*k² = ∑(每个元素*k)²,因此区间平方和直接乘k²即可

    3、两个标记,lazy1表示加,lazy2表示乘,如何Pushdown

    首先对于两个标记是先加还是先乘很难搞清,统一设为(xi+p1)*p2的形式,即lazy1要随着lazy2更新,每次对该区间进行乘操作时,lazy1也跟着*k,

    1. lazy1[p] *= num;
    2. lazy2[p] *=num;

    这时进行pushdown:

    先更新标记:

    1. lazy1[p*2] += lazy1[p];
    2. lazy1[p*2+1] += lazy1[p];
    3. lazy2[p*2] *= lazy2[p];
    4. lazy2[p*2+1] *= lazy2[p];

    ∑((xi+p1)*p2)² = ∑xi² * p2² + 2 * p2² * p1 * ∑xi + ∑p2² * p1²

    又因为p1即lazy1标记随着lazy2(p2)标记实时更新,因此此时lazy1[p] = p1*p2;

    说明:∑xi为区间和

    1. tree2[p*2] *= lazy2[p]*lazy2[p];
    2. tree2[p*2] += 2*tree1[p*2]*lazy1[p]*lazy2[p] + lazy1[p]*lazy1[p]*(mid-l+1);
    3. tree2[p*2+1] *= lazy2[p]*lazy2[p];
    4. tree2[p*2+1] += 2*tree1[p*2+1]*lazy1[p]*lazy2[p] + lazy1[p]*lazy1[p]*(r-(mid+1)+1);

    同样的分析对于区间和

    ∑((xi+p1)*p2) = ∑xi * p2 + 2*∑p2 * p1

    1. tree1[p*2] *= lazy2[p];
    2. tree1[p*2] += (mid-l+1)*lazy1[p];
    3. tree1[p*2+1] *= lazy2[p];
    4. tree1[p*2+1] += (r-(mid+1)+1)*lazy1[p];

    注意这里两个区间的更新不可以调换,因为区间平方和要利用区间和,因此区间平方和要先计算,如果调换,那么就会重复计算

    完整代码:

    1. # include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N = 10000+10;
    5. int n, m;
    6. ll a[N];
    7. ll tree1[N*4], tree2[N*4], lazy1[N*4], lazy2[N*4];
    8. void build(int p, int l, int r)
    9. {
    10. if (l == r)
    11. {
    12. tree1[p] = a[l];
    13. tree2[p] = a[l]*a[l];
    14. return ;
    15. }
    16. int mid = (l+r)/2;
    17. build(2*p, l, mid);
    18. build(2*p+1, mid+1, r);
    19. tree1[p] = tree1[p*2] + tree1[p*2+1];
    20. tree2[p] = tree2[p*2] + tree2[p*2+1];
    21. }
    22. void pushdown(int p, int l, int r)
    23. {
    24. lazy1[p*2] += lazy1[p];
    25. lazy1[p*2+1] += lazy1[p];
    26. lazy2[p*2] *= lazy2[p];
    27. lazy2[p*2+1] *= lazy2[p];
    28. int mid = (l+r)/2;
    29. tree2[p*2] *= lazy2[p]*lazy2[p];
    30. tree2[p*2] += 2*tree1[p*2]*lazy1[p]*lazy2[p] + lazy1[p]*lazy1[p]*(mid-l+1);
    31. tree2[p*2+1] *= lazy2[p]*lazy2[p];
    32. tree2[p*2+1] += 2*tree1[p*2+1]*lazy1[p]*lazy2[p] + lazy1[p]*lazy1[p]*(r-(mid+1)+1);
    33. tree1[p*2] *= lazy2[p];
    34. tree1[p*2] += (mid-l+1)*lazy1[p];
    35. tree1[p*2+1] *= lazy2[p];
    36. tree1[p*2+1] += (r-(mid+1)+1)*lazy1[p];
    37. lazy1[p] = 0;
    38. lazy2[p] = 1;
    39. }
    40. void change1(int p, int l, int r, int x, int y, ll num)//+num
    41. {
    42. if (x<=l && y>=r)
    43. {
    44. tree2[p] += 2*tree1[p]*num + num*num*(r-l+1);
    45. tree1[p] += num*(r-l+1);
    46. lazy1[p] += num;
    47. return ;
    48. }
    49. if (lazy1[p]!=0 || lazy2[p]!=1)
    50. pushdown(p, l, r);
    51. int mid = (l+r)/2;
    52. if (x<=mid) change1(2*p, l, mid, x, y, num);
    53. if (y>mid) change1(2*p+1, mid+1, r, x, y, num);
    54. tree1[p] = tree1[p*2] + tree1[p*2+1];
    55. tree2[p] = tree2[p*2] + tree2[p*2+1];
    56. }
    57. void change2(int p, int l, int r, int x, int y, ll num)//*num
    58. {
    59. if (x<=l && y>=r)
    60. {
    61. tree2[p] *= num*num;
    62. tree1[p] *= num;//单个影响
    63. lazy1[p] *= num;
    64. lazy2[p] *=num;
    65. return ;
    66. }
    67. if (lazy1[p]!=0 || lazy2[p]!=1)
    68. pushdown(p, l, r);
    69. int mid = (l+r)/2;
    70. if (x<=mid) change2(2*p, l, mid, x, y, num);
    71. if (y>mid) change2(2*p+1, mid+1, r, x, y, num);
    72. tree1[p] = tree1[p*2] + tree1[p*2+1];
    73. tree2[p] = tree2[p*2] + tree2[p*2+1];
    74. }
    75. ll cal1(int p, int l, int r, int x, int y)//求和
    76. {
    77. if (x<=l && y>=r) return tree1[p];
    78. if (lazy1[p]!=0 || lazy2[p]!=1)
    79. pushdown(p, l, r);
    80. int mid = (l+r)/2;
    81. // ll ans = 0;
    82. // if (x<=mid) ans += cal1(2*p, l, mid, x, y);
    83. // if (y>mid) ans += cal1(2*p+1, mid+1, r, x, y);
    84. // return ans;
    85. if (y<=mid) return cal1(2*p, l, mid, x, y);
    86. if (x>mid) return cal1(2*p+1, mid+1, r, x, y);
    87. return cal1(2*p, l, mid, x, mid) + cal1(2*p+1, mid+1, r, mid+1, y);
    88. }
    89. ll cal2(int p, int l, int r, int x, int y)//求平方和
    90. {
    91. if (x<=l && y>=r) return tree2[p];
    92. if (lazy1[p]!=0 || lazy2[p]!=1)
    93. pushdown(p, l, r);
    94. int mid = (l+r)/2;
    95. // ll ans = 0;
    96. // if (x<=mid) ans += cal2(2*p, l, mid, x, y);
    97. // if (y>mid) ans += cal2(2*p+1, mid+1, r, x, y);
    98. // return ans;
    99. if (y<=mid) return cal2(2*p, l, mid, x, y);
    100. if (x>mid) return cal2(2*p+1, mid+1, r, x, y);
    101. return cal2(2*p, l, mid, x, mid) + cal2(2*p+1, mid+1, r, mid+1, y);
    102. }
    103. int main()
    104. {
    105. for (int i=0; i4; i++)
    106. lazy2[i] = 1;
    107. memset(lazy1, 0, sizeof(lazy1));
    108. cin>>n>>m;
    109. for (int i=1; i<=n; i++)
    110. cin>>a[i];
    111. build(1, 1, n);
    112. for (int i=1; i<=m; i++)
    113. {
    114. int q;
    115. cin>>q;
    116. if (q == 1)
    117. {
    118. int l, r;
    119. cin>>l>>r;
    120. cout<<cal1(1, 1, n, l, r)<
    121. }
    122. if (q == 2)
    123. {
    124. int l, r;
    125. cin>>l>>r;
    126. cout<<cal2(1, 1, n, l, r)<
    127. }
    128. if (q == 3)
    129. {
    130. int l, r;
    131. ll x;
    132. cin>>l>>r>>x;
    133. change2(1, 1, n, l, r, x);
    134. }
    135. if (q == 4)
    136. {
    137. int l, r;
    138. ll x;
    139. cin>>l>>r>>x;
    140. change1(1, 1, n, l, r, x);
    141. }
    142. }
    143. return 0;
    144. }

  • 相关阅读:
    关于Redis集群的一些问题的理解
    创新之力迸发无限想象,联想创新开放日触见未来科技
    【前端进阶】-TypeScript高级类型 | 泛型约束、泛型接口、泛型工具类型
    【羊了个羊】背后的计算机网络原理
    【车载以太网测试从入门到精通】——DoIP BootLoader刷写测试(含CAPL源码)
    LeetCode220726_52、腐烂的橘子
    Python字符串操作:str.format
    DM8表空间备份还原
    用python统计文本字符出现的次数
    创新实战|高转化网站首页设计的10大关键要素
  • 原文地址:https://blog.csdn.net/m0_60531106/article/details/127820828