Advertisement
Guest User

Untitled

a guest
Mar 21st, 2019
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.30 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. ll MOD = 1000000007;
  8. ll dr[400000];
  9. ll pr[400000];
  10. ll sf[400000];
  11. ll w[400000];
  12. ll a[400000];
  13.  
  14.  
  15. void bl(ll v, ll l, ll r){
  16. if (r == l + 1){
  17. dr[v] = w[l];
  18. pr[v] = 0;
  19. sf[v] = 0;
  20. return;
  21. }
  22. bl(2 * v + 1, l, (l + r) / 2);
  23. bl(2 * v + 2, (l + r) / 2, r);
  24. dr[v] = dr[2 * v + 1] + dr[2 * v + 2];
  25. pr[v] = pr[2 * v + 1] + pr[2 * v + 2] + (a[r - 1] - (r - (l + r) / 2) - a[(r + l) / 2 - 1]) * dr[2 * v + 1];
  26. sf[v] = sf[2 * v + 1] + sf[2 * v + 2] + (a[(r + l) / 2] - a[l] - ((r + l) / 2 - l)) * dr[2 * v + 2];
  27. dr[v] %= MOD;
  28. sf[v] %= MOD;
  29. pr[v] %= MOD;
  30. }
  31.  
  32. void ch(ll v, ll l, ll r, ll id, ll x){
  33. if (r == l + 1 && l == id){
  34. dr[v] = x;
  35. pr[v] = 0;
  36. sf[v] = 0;
  37. return;
  38. }
  39. if (r <= id || l > id){
  40. return;
  41. }
  42. ch(2 * v + 1, l, (l + r) / 2, id, x);
  43. ch(2 * v + 2, (l + r) / 2, r, id, x);
  44. dr[v] = dr[2 * v + 1] + dr[2 * v + 2];
  45. pr[v] = pr[2 * v + 1] + pr[2 * v + 2] + (a[r - 1] - (r - (l + r) / 2) - a[(r + l) / 2 - 1]) * dr[2 * v + 1];
  46. sf[v] = sf[2 * v + 1] + sf[2 * v + 2] + (a[(r + l) / 2] - a[l] - ((r + l) / 2 - l)) * dr[2 * v + 2];
  47. dr[v] %= MOD;
  48. sf[v] %= MOD;
  49. pr[v] %= MOD;
  50. }
  51.  
  52.  
  53. ll sm(ll v, ll l, ll r, ll ln, ll rn){
  54. if (ln >= r || rn <= l){
  55. return 0;
  56. }
  57. if (ln <= l && r <= rn){
  58. return dr[v];
  59. }
  60. return (sm(2 * v + 1, l, (l + r) / 2, ln, rn) + sm(2 * v + 2, (l + r) / 2, r, ln, rn)) % MOD;
  61. }
  62.  
  63. ll prr(ll v, ll l, ll r, ll ln, ll k){
  64. if (ln >= r || k <= l){
  65. return 0;
  66. }
  67. if (ln <= l && r <= k){
  68. return (pr[v] + (a[k - 1] - (k - r) - a[r - 1]) * dr[v]) % MOD;
  69. }
  70. return (prr(2 * v + 1, l, (l + r) / 2, ln, k) + prr(2 * v + 2, (l + r) / 2, r, ln, k)) % MOD;
  71. }
  72.  
  73. ll sff(ll v, ll l, ll r, ll k, ll rn){
  74. if (k >= r || rn <= l){
  75. return 0;
  76. }
  77. if (k <= l && r <= rn){
  78. return (sf[v] + (a[l] - a[k] - (l - k)) * dr[v]) % MOD;
  79. }
  80. return (sff(2 * v + 1, l, (l + r) / 2, k, rn) + sff(2 * v + 2, (l + r) / 2, r, k, rn)) % MOD;
  81. }
  82.  
  83. int main() {
  84. ios::sync_with_stdio(0);
  85. cin.tie(0);
  86. ll n, q;
  87. cin >> n >> q;
  88. for (int i = 0; i < n; i++){
  89. cin >> a[i];
  90. }
  91. for (int i = 0; i < n; i++){
  92. cin >> w[i];
  93. }
  94. bl(0, 0, n);
  95. for (int i = 0; i < 3 * n; i++){
  96. cout << dr[i] << " ";
  97. }
  98. cout << endl;
  99.  
  100. for (int i = 0; i < 3 * n; i++){
  101. cout << pr[i] << " ";
  102. }
  103. cout << endl;
  104.  
  105. for (int i = 0; i < 3 * n; i++){
  106. cout << sf[i] << " ";
  107. }
  108. cout << endl;
  109.  
  110. for (int i = 0; i < q; i++){
  111. ll x, y;
  112. cin >> x >> y;
  113. if (x < 0){
  114. ch(0, 0, n, -x, y);
  115. }
  116. else{
  117. x--;
  118. ll L = x, R = y;
  119. while (R - L > 1){
  120. ll mm = (R + L) / 2;
  121. ll t1 = sm(0,0,n,L,mm), t2 = sm(0,0,n,mm,R);
  122. if (t1 < t2){
  123. L = mm;
  124. }
  125. else{
  126. R = mm;
  127. }
  128. }
  129. cout << x << " " << L << " mememme ";
  130. cout << prr(0,0,n,x,L) + sff(0,0,n,L,y) << endl;
  131. }
  132. }
  133.  
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement