Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.35 KB | None | 0 0
  1. #include <cstdio>
  2. #include <fstream>
  3. #include <iostream>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8.  
  9. long long f[1001][1001][4];
  10. int n;
  11. long long x, y;
  12.  
  13. long long get(long long x1, long long y1)
  14. {
  15.  
  16. int i = x1;
  17. long long ans = 0;
  18. while (i > 0)
  19. {
  20. int j = y1;
  21. while (j > 0)
  22. {
  23. ans += f[i][j][0] * x1 * y1;
  24. // cout << f[i][j][0] << " 0 " << i << " get " << j << endl;
  25. ans += f[i][j][1] * y1;
  26. // cout << f[i][j][1] << " 1 " << i << " get " << j << endl;
  27. ans += f[i][j][2] * x1;
  28. // cout << f[i][j][2] << " 2 " << i << " get " << j << endl;
  29. ans += f[i][j][3];
  30. // cout << f[i][j][3] << " 3 " << i << " get " << j << endl;
  31. j = j & (j - 1);
  32. }
  33. i = i & (i - 1);
  34. }
  35. return ans;
  36. }
  37.  
  38. void add(int x1, int y1, long long v)
  39. {
  40. int i = x1;
  41. while (i <= x)
  42. {
  43. // cout << "1";
  44. int j = y1;
  45. while (j <= y)
  46. {
  47. f[i][j][0] += v;
  48. // cout << f[i][j][0] << " 0 " << i << " " << j << endl;
  49. f[i][j][1] += v * (1 - x1);
  50. // cout << f[i][j][1] << " 1 " << i << " " << j << endl;
  51. f[i][j][2] += v * (1 - y1);
  52. // cout << f[i][j][2] << " 2 " << i << " " << j << endl;
  53. f[i][j][3] += v * (x1 - 1) * (y1 - 1);
  54. // cout << f[i][j][3] << " 3 " << i << " " << j << endl;
  55. j = (j | (j - 1)) + 1;
  56. // cout << "2";
  57. }
  58. i = (i | (i - 1)) + 1;
  59. }
  60. return;
  61. }
  62.  
  63.  
  64.  
  65. int main()
  66. {
  67.  
  68. freopen("segtree2d.in", "r", stdin);
  69. freopen("segtree2d.out", "w", stdout);
  70. int i;
  71. cin >> x >> y;
  72.  
  73. cin >> n;
  74.  
  75.  
  76. for (i = 0; i < n; i++)
  77. {
  78. int q;
  79. long long x1, y1, x2, y2, w;
  80. cin >> q >> x1 >> y1 >> x2 >> y2;
  81. if (q == 1)
  82. {
  83. cin >> w;
  84. add(x1, y1, w);
  85. // cout << "1";
  86. add(x2 + 1, y1, -w);
  87. // cout << "1";
  88. add(x1, y2 + 1, -w);
  89. // cout << "1";
  90. add(x2 + 1, y2 + 1, w);
  91. // cout << "1";
  92.  
  93. }
  94. else
  95. {
  96.  
  97. long long ans = get(x2, y2) - get(x1 - 1, y2) - get(x2, y1 - 1) + get(x1 - 1, y1 - 1);
  98. cout << ans << endl;
  99.  
  100. }
  101. }
  102.  
  103.  
  104. return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement