Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using std::vector;
- using std::cin;
- using std::cout;
- class Fenwick {
- public:
- Fenwick(int n): size_(n) {
- Vol.resize(size_, vector<vector<long long> >(size_, vector<long long> (size_, 0)));
- }
- long long Sum(int left_x, int left_y, int left_z,
- int right_x, int right_y, int right_z) const;
- void Update(int index_x, int index_y, int index_z, long long value);
- private:
- int size_;
- vector<vector<vector<long long> > > Vol;
- long long sum(int x, int y, int z) const;
- };
- long long Fenwick::Sum(int left_x, int left_y, int left_z,
- int right_x, int right_y, int right_z) const {
- --left_x;
- --left_y;
- --left_z;
- // Для подсчёта нужно воспользоваться
- // формулой включений и исключений
- return sum(right_x, right_y, right_z) -
- sum(right_x, right_y, left_z) -
- sum(left_x, right_y, right_z) -
- sum(right_x, left_y, right_z) +
- sum(left_x, right_y, left_z) +
- sum(right_x, left_y, left_z) +
- sum(left_x, left_y, right_z) -
- sum(left_x, left_y, left_z);
- }
- long long Fenwick::sum(int x, int y, int z) const {
- long long ans = 0;
- for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
- for (int j = y; j >= 0; j = (j & (j + 1)) - 1) {
- for (int k = z; k >= 0; k = (k & (k + 1)) - 1) {
- ans += Vol[i][j][k];
- }
- }
- }
- return ans;
- }
- void Fenwick::Update(int index_x, int index_y, int index_z, long long val) {
- for (int i = index_x; i < size_; i = i | (i + 1)) {
- for (int j = index_y; j < size_; j = j | (j + 1)) {
- for (int k = index_z; k < size_; k = k | (k + 1)) {
- Vol[i][j][k] += val;
- }
- }
- }
- }
- int main() {
- int n;
- cin >> n;
- Fenwick tree(n);
- int x;
- while (1) {
- cin >> x;
- if (x == 1) {
- int index_x, index_y, index_z;
- long long k;
- cin >> index_x >> index_y >> index_z >> k;
- tree.Update(index_x, index_y, index_z, k);
- } else if (x == 2) {
- int index_lx, index_ly, index_lz, index_rx, index_ry, index_rz;
- cin >> index_lx >> index_ly >> index_lz >>
- index_rx >> index_ry >> index_rz;
- long long res = tree.Sum(index_lx, index_ly, index_lz, index_rx, index_ry, index_rz);
- cout << res << "\n";
- } else {
- return 0;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement