Advertisement
Guest User

Untitled

a guest
Dec 8th, 2021
49
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.42 KB | None
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define ll long long
  4. #define si short int
  5. #define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  6. #define pill pair<ll,ll>
  7. #define f first
  8. #define s second
  9. #define pilc pair<ll,char>
  10. #define all(a) (a).begin(),(a).end()
  11. #define rep(s,e,step) for(int i = (s); i < (e) ; i += step)
  12. #define vrep(s,e,step) for(int j = (s); j < (e) ; j += step)
  13. #define ex exit(0)
  14. #define sz(a) (a).size()
  15.  
  16.  
  17. using namespace std;
  18.  
  19. const ll N = 5e5;
  20. const ll big = 1e18;
  21. const ll block = 800;
  22. const ll mod = 1e6;
  23. ll n, q;
  24. ll a[N];
  25. struct seg {
  26. ll t[4 * N] = {0};// ����� �� �������
  27. ll u[4 * N] = {0};// ���������� ������� ������� ������������ �� ���� �������
  28. ll up[4 * N] = {0};// ����� ������� ����� ��������� �� ���� ��������� �� �������
  29. // ����� ����� �� 1 �� n ��� (n * (n + 1)) / 2
  30. void push(ll v, ll tl, ll tr) {
  31. ll z = tr - tl + 1;
  32. t[v] += up[v] * z + u[v] * (z * (z + 1)) / 2;
  33. if(tl != tr) {
  34. ll m = (tl + tr) >> 1;
  35. up[v * 2] += up[v];
  36. up[v * 2 + 1] += up[v] + u[v] * (m - tl + 1);
  37. u[v * 2] += u[v];
  38. u[v * 2 + 1] += u[v];
  39. }
  40. u[v] = up[v] = 0;
  41. }
  42.  
  43. void bld(ll v = 1, ll tl = 1, ll tr = n) {
  44. if(tl == tr)
  45. return (void)(t[v] = a[tl]);
  46. ll m = (tl + tr) >> 1;
  47. bld(v * 2, tl, m);
  48. bld(v * 2 + 1, m + 1, tr);
  49. t[v] = t[v * 2] + t[v * 2 + 1];
  50. }
  51. void upd(ll l, ll r, ll v = 1, ll tl = 1, ll tr = n) {
  52. push(v, tl, tr);
  53. if(tl > r || tr < l)
  54. return;
  55. if(l <= tl && tr <= r) {
  56. up[v] += tl - l;
  57. u[v]++;
  58. push(v, tl, tr);
  59. return;
  60. }
  61. ll m = (tl + tr) >> 1;
  62. upd(l, r, v * 2, tl, m);
  63. upd(l, r, v * 2 + 1, m + 1, tr);
  64. t[v] = t[v * 2] + t[v * 2 + 1];
  65. }
  66. ll get(ll l, ll r, ll v = 1, ll tl = 1, ll tr = n) {
  67. push(v, tl, tr);
  68. if(tl > r || l > tr)
  69. return 0;
  70. if(l <= tl && tr <= r)
  71. return t[v];
  72. ll m = (tl + tr) >> 1;
  73. return (get(l, r, v * 2, tl, m) +
  74. get(l, r, v * 2 + 1, m + 1, tr));
  75. }
  76. } rt;
  77.  
  78. int main() {
  79. speed;
  80. cin >> n >> q;
  81. for(int i = 1; i <= n; i++)
  82. cin >> a[i];
  83. rt.bld();
  84. while(q--) {
  85. ll t, a, b;
  86. cin >> t >> a >> b;
  87. if(t == 1)
  88. rt.upd(a, b);
  89. else
  90. cout << rt.get(a, b) << '\n';
  91. }
  92. }
Advertisement
RAW Paste Data Copied
Advertisement