fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. const int N = 1e5 + 5;
  8.  
  9. int n, m, k;
  10. vector<vector<int>> pos, bit;
  11. vector<int> posX;
  12. struct query {
  13.     int type, l, r, u, v;
  14. };
  15. query Q[N];
  16.  
  17. inline void fakeUpX(int l) {
  18.     posX.push_back(l);
  19. }
  20. inline void fakeGetRectX(int l, int u) {
  21.     posX.push_back(u);
  22.     posX.push_back(l - 1);
  23. }
  24. inline void compressX() {
  25.     posX.push_back(-1);
  26.     sort(posX.begin(), posX.end());
  27.     posX.erase(unique(posX.begin(), posX.end()), posX.end());
  28.     pos.resize(posX.size(), {});
  29.     bit.resize(posX.size(), {});
  30. }
  31.  
  32. inline void fakeUp(int u, int v) {
  33.     for (int i = lower_bound(posX.begin(), posX.end(), u) - posX.begin(); i < pos.size(); i += i &- i) pos[i].push_back(v);
  34. }
  35.  
  36. inline void fakeGet(int u, int v) {
  37.     for (int i = lower_bound(posX.begin(), posX.end(), u) - posX.begin(); i; i -= i &- i) pos[i].push_back(v);
  38. }
  39.  
  40. inline void fakeGetRect(int l, int r, int u, int v) {
  41.     fakeGet(u, v);
  42.     fakeGet(l - 1, v);
  43.     fakeGet(u, r - 1);
  44.     fakeGet(l - 1, r - 1);
  45. }
  46.  
  47. inline void compress() {
  48.     for (int i = 1; i < pos.size(); i++) {
  49.         pos[i].push_back(-1);
  50.         sort(pos[i].begin(), pos[i].end());
  51.         pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());   
  52.         bit[i].resize(pos[i].size(), 0);
  53.     }
  54. }
  55. inline void update(int u, int v, int t) {
  56.     for (int i = lower_bound(posX.begin(), posX.end(), u) - posX.begin(); i < pos.size(); i += i &- i) {
  57.         for (int j = lower_bound(pos[i].begin(), pos[i].end(), v) - pos[i].begin(); j < pos[i].size(); j += j &- j) {
  58.             bit[i][j] += t;
  59.         }
  60.     }
  61. }
  62.  
  63. inline int get(int u, int v) {
  64.     int ans = 0;
  65.     for(int i = lower_bound(posX.begin(), posX.end(), u) - posX.begin(); i; i -= i &- i) {
  66.         for (int j = lower_bound(pos[i].begin(), pos[i].end(), v) - pos[i].begin(); j > 0; j -= j &- j) {
  67.             ans += bit[i][j];
  68.         }
  69.     }
  70.     return ans;
  71. }
  72. int getRect(int l, int r, int u, int v) {
  73.     return get(u, v) - get(l - 1, v) - get(u, r - 1) + get(l - 1, r - 1);
  74. }
  75.  
  76. using pii = pair<int, int>;
  77. map<pii, int> val;
  78. signed main() {
  79.     cin.tie(NULL)->sync_with_stdio(false);
  80.     if(ifstream("QUERY.inp")) {
  81.         freopen("QUERY.inp", "r", stdin);
  82.         freopen("QUERY.out", "w", stdout);
  83.     }
  84.     cin >> n >> m >> k;
  85.     for (int i = 1; i <= k; i++) {
  86.         char c; cin >> c;
  87.         if (c == 'S') {
  88.             Q[i].type = 1;
  89.             cin >> Q[i].l >> Q[i].r >> Q[i].u;
  90.             fakeUpX(Q[i].l);
  91.         }
  92.         else {
  93.             Q[i].type = 2;
  94.             cin >> Q[i].l >> Q[i].r >> Q[i].u >> Q[i].v;
  95.             fakeGetRectX(Q[i].l, Q[i].u);
  96.         }
  97.     }
  98.     compressX();
  99.     for (int i = 1; i <= k; i++) {
  100.         if (Q[i].type == 1) fakeUp(Q[i].l, Q[i].r);
  101.         else fakeGetRect(Q[i].l, Q[i].r, Q[i].u, Q[i].v);
  102.     }
  103.     compress();
  104.     for (int i = 1; i <= k; i++) {
  105.         if (Q[i].type == 1) {
  106.             if (val.count({Q[i].l, Q[i].r})) {
  107.                 Q[i].u -= val[{Q[i].l, Q[i].r}];
  108.             }
  109.             update(Q[i].l, Q[i].r, Q[i].u);
  110.             val[{Q[i].l, Q[i].r}] += Q[i].u;
  111.         }
  112.         else {
  113.             cout << getRect(Q[i].l, Q[i].r, Q[i].u, Q[i].v) << "\n";
  114.         }
  115.     }
  116.     return 0;
  117. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fllIKo
language:
C++14 (gcc 8.3)
created:
18 days ago
visibility:
public

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!