Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Слава Україні, Героям слава
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 1e3 + 7;
- namespace seg2d {
- long long seg[3 * N][3 * N];
- void addy(int y, int val, int pl, int pr = 1, int l = 1, int r = 1000) {
- seg[pl][pr] += val;
- if(l == r) {
- return;
- }
- int mid = (l + r) >> 1;
- if(y <= mid) {
- addy(y, val, pl, 2 * pr, l, mid);
- } else {
- addy(y, val, pl, 2 * pr + 1, mid + 1, r);
- }
- }
- void add(int x, int y, int val, int p = 1, int l = 1, int r = 1000) {
- addy(y, val, p);
- if(l == r) {
- return;
- }
- int mid = (l + r) >> 1;
- if(x <= mid) {
- add(x, y, val, 2 * p, l, mid);
- } else {
- add(x, y, val, 2 * p + 1, mid + 1, r);
- }
- }
- long long queryy(int y1, int y2, int pl, int pr = 1, int l = 1, int r = 1000) {
- if(r < y1 or l > y2) {
- return 0;
- }
- if(l >= y1 and r <= y2) {
- return seg[pl][pr];
- }
- int mid = (l + r) >> 1;
- return queryy(y1, y2, pl, 2 * pr, l, mid) + queryy(y1, y2, pl, 2 * pr + 1, mid + 1, r);
- }
- long long query(int x1, int y1, int x2, int y2, int p = 1, int l = 1, int r = 1000) {
- if(r < x1 or l > x2) {
- return 0;
- }
- if(l >= x1 and r <= x2) {
- return queryy(y1, y2, p);
- }
- int mid = (l + r) >> 1;
- return query(x1, y1, x2, y2, 2 * p, l, mid) + query(x1, y1, x2, y2, 2 * p + 1, mid + 1, r);
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int n, q;
- cin >> n >> q;
- vector<string> v(n);
- vector<vector<int>> a(n + 1, vector<int>(n + 1));
- for(int i = 0; i < n; i++) {
- cin >> v[i];
- }
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < n; j++) {
- a[i + 1][j + 1] = (v[i][j] == '*');
- seg2d::add(i + 1, j + 1, a[i + 1][j + 1]);
- }
- }
- while(q--) {
- int t;
- cin >> t;
- if(t == 1) {
- int x, y;
- cin >> x >> y;
- seg2d::add(x, y, (a[x][y] ^ 1) - a[x][y]);
- a[x][y] ^= 1;
- } else {
- int x1, y1, x2, y2;
- cin >> x1 >> y1 >> x2 >> y2;
- cout << seg2d::query(x1, y1, x2, y2) << "\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement