fork(3) download
copy 
  1. #include<bits/stdc++.h>
  2. #define rep(i,a,b) for(int i=a;i<b;i++)
  3. #define rrep(i,a,b) for(int i=a;i>=b;i--)
  4. #define fore(i,a) for(auto &i:a)
  5. #pragma GCC optimize ("-O3")
  6. using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
  7. //---------------------------------------------------------------------------------------------------
  8. typedef long long ll;
  9. #define def 0
  10. using V = ll;
  11. V comp(V& l, V& r) { return l + r; };
  12. struct SegTree { //[l,r)
  13.     int NV;
  14.     vector<V> val;
  15.     void init(int n) {
  16.         NV = 1;
  17.         while (NV < n) NV *= 2;
  18.         val = vector<V>(NV * 2, def);
  19.     }
  20.     V get(int x, int y, int l, int r, int k) {
  21.         if (r <= x || y <= l) return def; if (x <= l&&r <= y)return val[k];
  22.         auto a = get(x, y, l, (l + r) / 2, k * 2); auto b = get(x, y, (l + r) / 2, r, k * 2 + 1); return comp(a, b);
  23.     }
  24.     V get(int x, int y) { return get(x, y, 0, NV, 1); }
  25.     void update(int i, V v) { i += NV; val[i] = v; while (i>1)i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]); }
  26.     void add(int i, V v) { update(i, val[i + NV] + v); }
  27.     V operator[](int x) { return get(x, x + 1); }
  28. };
  29.  
  30. struct Healthy2DSegTree {
  31.     int NV;
  32.     vector<SegTree> st;
  33.     vector<vector<int>> index;
  34.  
  35.     void init(vector<vector<int>> &v) {
  36.         int n = v.size();
  37.         NV = 1; while (NV < n) NV *= 2;
  38.         index.resize(2 * NV);
  39.         rep(i, 0, n) fore(j, v[i]) index[i + NV].push_back(j);
  40.         rrep(i, NV * 2 - 1, 1) {
  41.             sort(index[i].begin(), index[i].end());
  42.             index[i].erase(unique(index[i].begin(), index[i].end()), index[i].end());
  43.             fore(j, index[i]) index[i / 2].push_back(j);
  44.         }
  45.         st.resize(2 * NV);
  46.         rep(i, 1, NV * 2) st[i].init(index[i].size());
  47.     }
  48.     void update(int x, int y, V v) {
  49.         assert(x < NV);
  50.         x += NV;
  51.         while (x) {
  52.             int yy = lower_bound(index[x].begin(), index[x].end(), y) - index[x].begin();
  53.             assert(yy != index[x].size());
  54.             assert(y == index[x][yy]);
  55.             st[x].update(yy, v);
  56.             x >>= 1;
  57.         }
  58.     }
  59.     void add(int x, int y, V v) {
  60.         assert(x < NV);
  61.         x += NV;
  62.         while (x) {
  63.             int yy = lower_bound(index[x].begin(), index[x].end(), y) - index[x].begin();
  64.             assert(yy != index[x].size());
  65.             assert(y == index[x][yy]);
  66.             st[x].add(yy, v);
  67.             x >>= 1;
  68.         }
  69.     }
  70.     V get(int sx, int tx, int sy, int ty, int k, int l, int r) {
  71.         assert(k < NV * 2);
  72.         assert(l < r);
  73.         if (r <= sx or tx <= l) return def;
  74.         if (sx <= l and r <= tx) {
  75.             int syy = lower_bound(index[k].begin(), index[k].end(), sy) - index[k].begin();
  76.             int tyy = lower_bound(index[k].begin(), index[k].end(), ty) - index[k].begin();
  77.             return st[k].get(syy, tyy);
  78.         }
  79.         int md = (l + r) / 2;
  80.         V le = get(sx, tx, sy, ty, k * 2, l, md);
  81.         V ri = get(sx, tx, sy, ty, k * 2 + 1, md, r);
  82.         return comp(le, ri);
  83.     }
  84.     V get(int sx, int tx, int sy, int ty) {
  85.         return get(sx, tx, sy, ty, 1, 0, NV);
  86.     }
  87. };
  88. /*---------------------------------------------------------------------------------------------------
  89. 　　　　　　　　　　　 ∧＿∧  
  90. 　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
  91. 　　　　 （ ´_ゝ`）　/　 ⌒i     
  92. 　　　　／　　　＼　 　  |　|     
  93. 　　　 /　　 /￣￣￣￣/　　|  
  94. 　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
  95. 　 　　　＼/＿＿＿＿/　（u　⊃  
  96. ---------------------------------------------------------------------------------------------------*/
  97.  
  98.  
  99.  
  100. int H, W, Q;
  101. vector<vector<int>> query;
  102. //---------------------------------------------------------------------------------------------------
  103. void _main() {
  104.     cin >> H >> W >> Q;
  105.     rep(i, 0, Q) {
  106.         int t; cin >> t;
  107.         if (t == 1) {
  108.             int x, y, v; cin >> x >> y >> v;
  109.             query.push_back({ t, x, y, v });
  110.         }
  111.         else {
  112.             int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;
  113.             query.push_back({ t, sx, sy, tx, ty });
  114.         }
  115.     }
  116.  
  117.     Healthy2DSegTree st;
  118.     vector<vector<int>> index(W);
  119.     rep(i, 0, Q) {
  120.         if (query[i][0] == 1) {
  121.             int x = query[i][1];
  122.             int y = query[i][2];
  123.             index[x].push_back(y);
  124.         }
  125.     }
  126.     st.init(index);
  127.  
  128.     rep(i, 0, Q) {
  129.         if (query[i][0] == 1) {
  130.             int x = query[i][1];
  131.             int y = query[i][2];
  132.             int v = query[i][3];
  133.             st.add(x, y, v);
  134.         } else {
  135.             int sx = query[i][1];
  136.             int sy = query[i][2];
  137.             int tx = query[i][3];
  138.             int ty = query[i][4];
  139.             ll ans = st.get(sx, tx + 1, sy, ty + 1);
  140.             printf("%lld\n", ans);
  141.         }
  142.     }
  143. }
Success #stdin #stdout 0s 4208KB
comments (?)
stdin
copy 
8 8 5
1 2 4 1
1 5 3 6
1 3 3 2
2 0 0 4 4
2 2 2 5 5
stdout
copy 
3
9
https://ideone.com/1LDC1V
language:
C++14 (gcc 8.3)
created:
7 years 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!