Advertisement
cosenza987

Untitled

Mar 10th, 2023
667
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.43 KB | None | 0 0
  1. //Слава Україні, Героям слава
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 1e3 + 7;
  8.  
  9. namespace seg2d {
  10.     long long seg[3 * N][3 * N];
  11.     void addy(int y, int val, int pl, int pr = 1, int l = 1, int r = 1000) {
  12.         seg[pl][pr] += val;
  13.         if(l == r) {
  14.             return;
  15.         }
  16.         int mid = (l + r) >> 1;
  17.         if(y <= mid) {
  18.             addy(y, val, pl, 2 * pr, l, mid);
  19.         } else {
  20.             addy(y, val, pl, 2 * pr + 1, mid + 1, r);
  21.         }
  22.     }
  23.     void add(int x, int y, int val, int p = 1, int l = 1, int r = 1000) {
  24.         addy(y, val, p);
  25.         if(l == r) {
  26.             return;
  27.         }
  28.         int mid = (l + r) >> 1;
  29.         if(x <= mid) {
  30.             add(x, y, val, 2 * p, l, mid);
  31.         } else {
  32.             add(x, y, val, 2 * p + 1, mid + 1, r);
  33.         }
  34.     }
  35.     long long queryy(int y1, int y2, int pl, int pr = 1, int l = 1, int r = 1000) {
  36.         if(r < y1 or l > y2) {
  37.             return 0;
  38.         }
  39.         if(l >= y1 and r <= y2) {
  40.             return seg[pl][pr];
  41.         }
  42.         int mid = (l + r) >> 1;
  43.         return queryy(y1, y2, pl, 2 * pr, l, mid) + queryy(y1, y2, pl, 2 * pr + 1, mid + 1, r);
  44.     }
  45.     long long query(int x1, int y1, int x2, int y2, int p = 1, int l = 1, int r = 1000) {
  46.         if(r < x1 or l > x2) {
  47.             return 0;
  48.         }
  49.         if(l >= x1 and r <= x2) {
  50.             return queryy(y1, y2, p);
  51.         }
  52.         int mid = (l + r) >> 1;
  53.         return query(x1, y1, x2, y2, 2 * p, l, mid) + query(x1, y1, x2, y2, 2 * p + 1, mid + 1, r);
  54.     }
  55. }
  56.  
  57. int main() {
  58.     ios_base::sync_with_stdio(false);
  59.     cin.tie(nullptr);
  60.     int n, q;
  61.     cin >> n >> q;
  62.     vector<string> v(n);
  63.     vector<vector<int>> a(n + 1, vector<int>(n + 1));
  64.     for(int i = 0; i < n; i++) {
  65.         cin >> v[i];
  66.     }
  67.     for(int i = 0; i < n; i++) {
  68.         for(int j = 0; j < n; j++) {
  69.             a[i + 1][j + 1] = (v[i][j] == '*');
  70.             seg2d::add(i + 1, j + 1, a[i + 1][j + 1]);
  71.         }
  72.     }
  73.     while(q--) {
  74.         int t;
  75.         cin >> t;
  76.         if(t == 1) {
  77.             int x, y;
  78.             cin >> x >> y;
  79.             seg2d::add(x, y, (a[x][y] ^ 1) - a[x][y]);
  80.             a[x][y] ^= 1;
  81.         } else {
  82.             int x1, y1, x2, y2;
  83.             cin >> x1 >> y1 >> x2 >> y2;
  84.             cout << seg2d::query(x1, y1, x2, y2) << "\n";
  85.         }
  86.     }
  87.     return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement