Advertisement
KShah

Untitled

Nov 21st, 2021
263
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using std::vector;
  5. using std::cin;
  6. using std::cout;
  7.  
  8. class Fenwick {
  9. public:
  10. Fenwick(int n): size_(n) {
  11. Vol.resize(size_, vector<vector<long long> >(size_, vector<long long> (size_, 0)));
  12. }
  13.  
  14. long long Sum(int left_x, int left_y, int left_z,
  15. int right_x, int right_y, int right_z) const;
  16. void Update(int index_x, int index_y, int index_z, long long value);
  17.  
  18. private:
  19. int size_;
  20. vector<vector<vector<long long> > > Vol;
  21.  
  22. long long sum(int x, int y, int z) const;
  23. };
  24.  
  25.  
  26. long long Fenwick::Sum(int left_x, int left_y, int left_z,
  27. int right_x, int right_y, int right_z) const {
  28. --left_x;
  29. --left_y;
  30. --left_z;
  31. // Для подсчёта нужно воспользоваться
  32. // формулой включений и исключений
  33. return sum(right_x, right_y, right_z) -
  34. sum(right_x, right_y, left_z) -
  35. sum(left_x, right_y, right_z) -
  36. sum(right_x, left_y, right_z) +
  37. sum(left_x, right_y, left_z) +
  38. sum(right_x, left_y, left_z) +
  39. sum(left_x, left_y, right_z) -
  40. sum(left_x, left_y, left_z);
  41. }
  42.  
  43. long long Fenwick::sum(int x, int y, int z) const {
  44. long long ans = 0;
  45. for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
  46. for (int j = y; j >= 0; j = (j & (j + 1)) - 1) {
  47. for (int k = z; k >= 0; k = (k & (k + 1)) - 1) {
  48. ans += Vol[i][j][k];
  49. }
  50. }
  51. }
  52. return ans;
  53. }
  54.  
  55. void Fenwick::Update(int index_x, int index_y, int index_z, long long val) {
  56. for (int i = index_x; i < size_; i = i | (i + 1)) {
  57. for (int j = index_y; j < size_; j = j | (j + 1)) {
  58. for (int k = index_z; k < size_; k = k | (k + 1)) {
  59. Vol[i][j][k] += val;
  60. }
  61. }
  62. }
  63. }
  64.  
  65.  
  66. int main() {
  67. int n;
  68. cin >> n;
  69. Fenwick tree(n);
  70. int x;
  71. while (1) {
  72. cin >> x;
  73. if (x == 1) {
  74. int index_x, index_y, index_z;
  75. long long k;
  76. cin >> index_x >> index_y >> index_z >> k;
  77. tree.Update(index_x, index_y, index_z, k);
  78. } else if (x == 2) {
  79. int index_lx, index_ly, index_lz, index_rx, index_ry, index_rz;
  80. cin >> index_lx >> index_ly >> index_lz >>
  81. index_rx >> index_ry >> index_rz;
  82. long long res = tree.Sum(index_lx, index_ly, index_lz, index_rx, index_ry, index_rz);
  83. cout << res << "\n";
  84. } else {
  85. return 0;
  86. }
  87. }
  88. }
  89.  
  90.  
  91.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement