fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1005;
  6.  
  7. int n, m, q; 
  8.  
  9. short g[N][N];
  10. short h[N][N];
  11. short v[N][N];
  12.  
  13. bitset<N> Q[N];
  14.  
  15. struct DSURollBack {
  16.  
  17.     vector<int> e;
  18.  
  19.     void init(int n) {
  20.         e = vector<int>(n, -1);
  21.         for (int i = 0; i < n; i++) 
  22.             Q[i / m][i % m] = 1;
  23.     }
  24.  
  25.     int get(int x) { return e[x] < 0 ? x : get(e[x]); }
  26.     bool same_set(int a, int b) { return get(a) == get(b); }
  27.     int size(int x) { return -e[get(x)]; }
  28.  
  29.     vector<array<int, 4>> mod;
  30.  
  31.     bool unite(int x, int y) {
  32.         x = get(x), y = get(y);
  33.         if (x == y) {
  34.             mod.push_back({-1, -1, -1, -1});
  35.             return 0;
  36.         }
  37.         if (e[x] > e[y]) swap(x, y);
  38.         mod.push_back({x, y, e[x], e[y]});
  39.         e[x] += e[y], e[y] = x;
  40.         Q[y / m][y % m] = 0;
  41.         return true;
  42.     }
  43.  
  44.     void rollback() {
  45.         auto a = mod.back();
  46.         mod.pop_back();
  47.         if (a[0] != -1) {
  48.             e[a[0]] = a[2];
  49.             e[a[1]] = a[3];
  50.             Q[a[1] / m][a[1] % m] = 1;
  51.         }
  52.     }
  53. };
  54.  
  55. struct OfflineDynamicConnectivity {
  56.     DSURollBack D;
  57.  
  58.     int sz;
  59.  
  60.     vector<vector<pair<int, int>>> seg;
  61.     vector<vector<array<int, 4>>> queries;
  62.  
  63.     vector<int> ans;
  64.  
  65.     void upd(int l, int r, pair<int, int> p) {
  66.         if (l > r) return;
  67.         for (l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
  68.             if (l & 1) seg[l++].push_back(p);
  69.             if (r & 1) seg[--r].push_back(p);
  70.         }
  71.     }
  72.  
  73.     void process(int ind) {
  74.         for (auto& t : seg[ind]) {
  75.             D.unite(t.first, t.second);
  76.         }
  77.         if (ind >= sz) {
  78.             int ti = ind - sz; 
  79.             for (auto& qq : queries[ti]) {
  80.                 int x1 = qq[0];
  81.                 int y1 = qq[1];
  82.                 int x2 = qq[2];
  83.                 int y2 = qq[3];
  84.                 int res = 0;
  85.                 for (int x = x1; x <= x2; x++) {
  86.                     bitset<N> b = Q[x] << (N - 1 - y2);
  87.                     b >>= (y1 + N - y2 - 1);
  88.                     res += b.count();
  89.                 }
  90.                 ans.push_back(res);
  91.             }
  92.         } else {
  93.             process(2 * ind); process(2 * ind + 1);
  94.         }
  95.         for (auto& t : seg[ind]) {
  96.             D.rollback();
  97.         }
  98.     }
  99.  
  100.     void add_query(int ti, array<int, 4> query) {
  101.         queries[ti].push_back(query);
  102.     }
  103.  
  104.     void init(int max_time) {
  105.         sz = 1;
  106.         while (sz < max_time) sz *= 2;
  107.         seg.assign(2 * sz, {});
  108.         queries.assign(sz, {});
  109.         D.init(n * m);
  110.     }
  111.  
  112.     vector<int> solve() {
  113.         process(1);
  114.         return ans;
  115.     }
  116. };
  117.  
  118. OfflineDynamicConnectivity O;
  119.  
  120. int main() {
  121.     cin.tie(0)->sync_with_stdio(0);
  122.  
  123.     cin >> n >> m >> q;
  124.  
  125.     for (int i = 0; i < N; i++) 
  126.         for (int j = 0; j < N; j++)
  127.             g[i][j] = h[i][j] = v[i][j] = -1;
  128.  
  129.     for (int i = 0; i < n; i++) {        
  130.         string line; cin >> line;
  131.         for (int j = 0; j < m; j++)
  132.             g[i][j] = line[j] - 'A';
  133.     }
  134.  
  135.     for (int i = 0; i < n; i++) {
  136.         for (int j = 0; j < m; j++) {
  137.             if (g[i][j] == g[i][j + 1]) 
  138.                 h[i][j] = 0;
  139.             if (g[i][j] == g[i + 1][j]) 
  140.                 v[i][j] = 0;
  141.         }
  142.     }
  143.  
  144.     auto conv = [&](int i, int j) -> int { return i * m + j; };
  145.  
  146.     auto hedge = [&](int i, int j) -> pair<int, int> {
  147.         if (g[i][j] != g[i][j + 1]) 
  148.             return {-1, -1};
  149.         return {conv(i, j), conv(i, j + 1)};
  150.     };
  151.  
  152.     auto vedge = [&](int i, int j) -> pair<int, int> {
  153.         if (g[i][j] != g[i + 1][j]) 
  154.             return {-1, -1};
  155.         return {conv(i, j), conv(i + 1, j)};
  156.     };
  157.  
  158.     O.init(q + 2);
  159.  
  160.     for (int qq = 1; qq <= q; qq++) {
  161.         int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
  162.         x1--, y1--, x2--, y2--;
  163.  
  164.         if (x1 != 0) { 
  165.             for (int y = y1; y <= y2; y++) {
  166.                 int t = v[x1 - 1][y];
  167.                 auto e = vedge(x1 - 1, y);
  168.                 if (e.first != -1) {
  169.                     O.upd(t, qq - 1, e);
  170.                     v[x1 - 1][y] = qq + 1;
  171.                 }
  172.             }
  173.         }
  174.  
  175.         if (y1 != 0) {
  176.             for (int x = x1; x <= x2; x++) {
  177.                 int t = h[x][y1 - 1];
  178.                 auto e = hedge(x, y1 - 1);
  179.                 if (e.first != -1) {
  180.                     O.upd(t, qq - 1, e);
  181.                     h[x][y1 - 1] = qq + 1;
  182.                 }
  183.             }
  184.         }
  185.  
  186.         if (x2 != n - 1) {
  187.             for (int y = y1; y <= y2; y++) {
  188.                 int t = v[x2][y];
  189.                 auto e = vedge(x2, y);
  190.                 if (e.first != -1) {
  191.                     O.upd(t, qq - 1, e);
  192.                     v[x2][y] = qq + 1;
  193.                 }
  194.             }
  195.         }
  196.  
  197.         if (y2 != m - 1) {
  198.             for (int x = x1; x <= x2; x++) {
  199.                 int t = h[x][y2];
  200.                 auto e = hedge(x, y2);
  201.                 if (e.first != -1) {
  202.                     O.upd(t, qq - 1, e);
  203.                     h[x][y2] = qq + 1;
  204.                 }
  205.             }
  206.         }
  207.  
  208.         O.add_query(qq, {x1, y1, x2, y2});
  209.     }
  210.  
  211.     for (int i = 0; i < n; i++) {
  212.         for (int j = 0; j < m; j++) {
  213.             if (v[i][j] != -1) 
  214.                 O.upd(v[i][j], q + 1, vedge(i, j));
  215.             if (h[i][j] != -1) 
  216.                 O.upd(h[i][j], q + 1, hedge(i, j));
  217.         }
  218.     }
  219.  
  220.     auto ans = O.solve();
  221.  
  222.     for (auto& t : ans) 
  223.         cout << t << '\n';
  224.  
  225.     return 0;
  226. }
Success #stdin #stdout 0s 9416KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/8j5VgP
language:
C++14 (gcc 8.3)
created:
3 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!