fork download
copy 
  1. // Input format:
  2. // First line contains n, m and q, where n and m - the size of the matrix , q is tne number of query.
  3. // n, m, q are positive integer and must not exceed 10^5.
  4. // The matrix is initially 0.
  5. // q following lines contains queries of 2 types:
  6. // 1 r c val - change the value of the cell (r, c) to val.
  7. // 2 r1 c1 r2 c2 - output the sum of the cell inside the submatrix (r1, c1, r2, c2)
  8. // 
  9. // r, r1, r2 must be positive integer and must not exceed n
  10. // c, c1, c2 must be positive integer and must not exceed m
  11. // val must be an integer fit in 32 bit inger.
  12.  
  13. // #define testing   // turn on self testing mode. i.e. check with the naive solution  
  14. #include <bits/stdc++.h>
  15. using namespace std;
  16. using llong = long long;
  17.  
  18. struct Upd {
  19.     int r, c, val, id;
  20.     Upd(int r_, int c_, int v, int i): r(r_), c(c_), val(v), id(i) {
  21.         --r;
  22.         --c;
  23.     }
  24. };
  25.  
  26. struct Qr {
  27.     int r1, c1, r2, c2, id;
  28.     Qr(int r1_, int c1_, int r2_, int c2_, int i)
  29.         : r1(r1_ - 1), c1(c1_ - 1), r2(r2_ - 1), c2(c2_ - 1), id(i) 
  30.     {
  31.         if (r1 > r2) swap(r1, r2);
  32.         if (c1 > c2) swap(c1, c2);
  33.     }
  34. };
  35.  
  36. int n, m, q;
  37.  
  38. vector<Upd> updates;
  39. vector<Qr> queries;
  40. void read(){
  41.     cin >> n >> m >> q;
  42.     updates.clear();
  43.     queries.clear();
  44.     for (int i = 0; i < q; ++i) {
  45.         int type; cin >> type;
  46.         if (type == 1) {
  47.             int r, c, v; cin >> r >> c >> v;
  48.             updates.emplace_back(r, c, v, i);
  49.         } else {
  50.             int r1, c1, r2, c2;
  51.             cin >> r1 >> c1 >> r2 >> c2;
  52.             queries.emplace_back(r1, c1, r2, c2, i);
  53.         }
  54.     }
  55. }
  56.  
  57. vector<llong> solve() {
  58.     // first we need to change the update from "change to" to "change by" to use with BIT
  59.     map<pair<int, int>, int> old_values;
  60.     for (auto& [r, c, v, i]: updates) {
  61.         pair<int, int> p {r, c};
  62.         v -= old_values[p];
  63.         old_values[p] += v;
  64.     }
  65.  
  66.     struct BIT {
  67.         vector<llong> sum;
  68.         vector<bool> is_changed;
  69.         vector<int> changed_elm;
  70.         BIT(int sz): sum(sz + 10), is_changed(sz + 10) {}
  71.         void roll_back() {
  72.             for (auto c: changed_elm) {
  73.                 is_changed[c] = 0;
  74.                 sum[c] = 0;
  75.             }
  76.             changed_elm.clear();
  77.         }
  78.         void upd(int p, int val) {
  79.             for (++p; p < (int)sum.size(); p += p & -p) {
  80.                 sum[p] += val;
  81.                 if (!is_changed[p]) {
  82.                     is_changed[p] = true;
  83.                     changed_elm.push_back(p);
  84.                 }
  85.             }
  86.         }
  87.         llong get(int p) {
  88.             llong ans = 0;
  89.             for (++p; p > 0; p -= p & -p) ans += sum[p];
  90.             return ans;
  91.         }
  92.  
  93.         llong get(int l, int r) {
  94.             return get(r) - get(l - 1);
  95.         }
  96.     };
  97.  
  98.     vector<vector<Upd>> upd_it(2 * n);
  99.     vector<vector<Qr>> qr_it(2 * n);
  100.  
  101.     for (auto u: updates) {
  102.         for (int p = n + u.r; p > 0; p >>= 1)
  103.             upd_it[p].push_back(u);
  104.     }
  105.     for (auto qr: queries) {
  106.         for (int l = qr.r1 + n, r = qr.r2 + n + 1; l < r; l >>= 1, r >>= 1) {
  107.             if (l & 1) qr_it[l++].push_back(qr);
  108.             if (r & 1) qr_it[--r].push_back(qr);
  109.         }
  110.     }
  111.  
  112.     BIT bit(m);
  113.     vector<llong> ans(q);
  114.     for (int root = 1; root < 2 * n; ++root) {
  115.         auto& ui = upd_it[root];
  116.         auto& qi = qr_it[root];
  117.         if (ui.empty() or qi.empty()) continue;
  118.  
  119.         int ptr = 0;
  120.         for (auto qr: qi) {
  121.             while (ptr < (int)ui.size() and ui[ptr].id < qr.id) {
  122.                 bit.upd(ui[ptr].c, ui[ptr].val);
  123.                 ++ptr;
  124.             }
  125.             ans[qr.id] += bit.get(qr.c1, qr.c2);
  126.         }
  127.         bit.roll_back();
  128.     }
  129.     int new_size = 0;
  130.     for (auto qr: queries) {
  131.         ans[new_size++] = ans[qr.id];
  132.     }
  133.     ans.resize(new_size);
  134.     return ans;
  135. }
  136.  
  137. mt19937 rng;
  138. #define rand() ((int)(rng() >> 1))
  139. void gen_test();
  140. void check_small_test();
  141. vector<llong> brute();
  142.  
  143. int main() {
  144. #ifdef testing
  145.     // rng.seed((llong)(main) ^ (llong)time(0)); 
  146.     while (true) {
  147.         gen_test();
  148.         auto exp = brute();
  149.         auto ans = solve();
  150.         if (exp == ans) {
  151.             cout << "Nice" << endl;
  152.             continue;
  153.         }
  154.         cout << "failed " << endl;
  155.         for (auto i: ans) cout << i << '\n';
  156.         cout << "---------------------\n";
  157.         for (auto i: exp) cout << i << '\n';
  158.         return 1;
  159.     }
  160. #endif
  161. #ifdef LOCAL
  162.     freopen("main.inp", "r", stdin);
  163.     freopen("main.out", "w", stdout);
  164. #endif
  165.     read();
  166.     // auto ans = brute();   
  167.     auto ans = solve();  
  168.     for (auto i: ans) cout << i << '\n';
  169.     return 0;
  170. }
  171.  
  172. ///////////////////////////////////////////////////////////////////////////////////
  173. void gen_test() {
  174.     ofstream inp("main.inp");
  175.     n = rand() % 10 + 1;
  176.     m = rand() % 10 + 1;
  177.     q = rand() % 10 + 1;
  178.     inp << n << ' ' << m << ' ' << q << '\n';
  179.  
  180.     updates.clear();
  181.     queries.clear();
  182.     for (int i = 0; i < q; ++i) {
  183.         int type = rand() & 1;
  184.         if (type == 1) {
  185.             int r, c, v;
  186.             r = rand() % n + 1;
  187.             c = rand() % m + 1;
  188.             v = rand() % 100;
  189.             updates.emplace_back(r, c, v, i);
  190.             inp << 1 << ' ' << r << ' ' << c << ' ' << v << '\n';
  191.         } else {
  192.             int r1, c1, r2, c2;
  193.             r1 = rand() % n + 1;
  194.             r2 = rand() % n + 1;
  195.             c1 = rand() % m + 1;
  196.             c2 = rand() % m + 1;
  197.             queries.emplace_back(r1, c1, r2, c2, i);
  198.             inp << 2 << ' ' << r1 << ' ' << c1 << ' ' << r2 << ' ' << c2 << '\n';
  199.         }
  200.     }
  201. }
  202.  
  203.  
  204. vector<llong> brute() {
  205.     int ptr = 0;
  206.     vector<llong> ans;
  207.     vector<vector<llong>> matrix(n, vector<llong>(m));
  208.     for (auto [r1, c1, r2, c2, id]: queries) {
  209.         while (ptr < (int)updates.size() and updates[ptr].id < id) {
  210.             matrix[updates[ptr].r][updates[ptr].c] = updates[ptr].val;
  211.             ++ptr;
  212.         }
  213.         llong cur_ans = 0;
  214.         for (int r = r1; r <= r2; ++r)
  215.         for (int c = c1; c <= c2; ++c) cur_ans += matrix[r][c];
  216.         ans.push_back(cur_ans);
  217.     }
  218.     return ans;
  219. }
  220.  
  221.  
Success #stdin #stdout 0s 4860KB
comments (?)
stdin
copy 
3 3 8
1 1 1 3
2 1 1 2 2
2 2 2 3 3
1 2 2 7
2 1 1 1 1
2 2 2 2 2
2 1 1 2 2
2 3 3 3 3
stdout
copy 
3
0
3
7
10
0
https://ideone.com/xgQ0Kk
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!