fork(1) download
copy 
  1. /*
  2.     author: kartik8800
  3. */
  4. #include<bits/stdc++.h>
  5. #define ll long long
  6. #define pb push_back
  7. #define fr(a,b) for(ll i = a; i < b; i++)
  8. #define mod 1000000007
  9. #define inf (1LL<<60)
  10. #define all(x) (x).begin(), (x).end()
  11. #define prDouble(x) cout << fixed << setprecision(10) << x
  12. #define triplet pair<ll,pair<ll,ll>>
  13. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  14. using namespace std;
  15.  
  16. struct FenwickTree {
  17.     vector<int> bit;  // binary indexed tree
  18.     int n;
  19.  
  20.     FenwickTree(int n) {
  21.         this->n = n;
  22.         bit.assign(n, 0);
  23.     }
  24.  
  25.     FenwickTree(vector<int> a) : FenwickTree(a.size()) {
  26.         for (size_t i = 0; i < a.size(); i++)
  27.             add(i, a[i]);
  28.     }
  29.  
  30.     int sum(int r) {
  31.         int ret = 0;
  32.         for (; r >= 0; r = (r & (r + 1)) - 1)
  33.             ret += bit[r];
  34.         return ret;
  35.     }
  36.  
  37.     int sum(int l, int r) {
  38.         return sum(r) - sum(l - 1);
  39.     }
  40.  
  41.     void add(int idx, int delta) {
  42.         for (; idx < n; idx = idx | (idx + 1))
  43.             bit[idx] += delta;
  44.     }
  45. };
  46.  
  47. int sum(int x, int y){return x + y;}
  48.  
  49. bool grid[1001][1001];
  50. int dp[1001][1001];
  51. vector<FenwickTree> row_updates(1001, FenwickTree(1001));
  52.  
  53. void build_dp(int n, int m)
  54. {
  55.     dp[0][0] = dp[1][0] = dp[0][1] = 0;
  56.  
  57.     for(int i = 1; i <= n; i++)
  58.     {
  59.         for(int j = 1; j <= n; j++)
  60.             dp[i][j] = grid[i][j] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1];
  61.     }
  62. }
  63.  
  64. void update(int i, int j, int n)
  65. {
  66.     int delta = -1;
  67.     if(grid[i][j] == 0) // it was empty
  68.         delta = 1; // now it has a tree
  69.  
  70.     grid[i][j] = !grid[i][j]; // switch the state
  71.     for(int k = i; k <= n; k++)
  72.         row_updates[k].add(j, delta);
  73. }
  74.  
  75. int getDP(int x, int y)
  76. {
  77.     return dp[x][y] + row_updates[x].sum(y);
  78. }
  79.  
  80. int query(int x1, int y1, int x2, int y2)
  81. {
  82.     return getDP(x2,y2) - getDP(x2,y1-1) - getDP(x1-1,y2) + getDP(x1-1,y1-1);
  83. }
  84.  
  85. int main() {
  86.    fast_io;
  87.    int n,q;
  88.    cin >> n >> q;
  89.  
  90.    for(int i = 1; i <= n; i++)
  91.    {
  92.        for(int j = 1; j <= n; j++)
  93.        {
  94.            char ch;
  95.            cin >> ch;
  96.            if(ch == '*')
  97.                 grid[i][j] = 1;
  98.            else grid[i][j] = 0;
  99.        }
  100.    }
  101.  
  102.    build_dp(n,n);
  103.  
  104.    while(q--)
  105.    {
  106.         int t;
  107.         cin >> t;
  108.         if(t == 1)
  109.         {
  110.             int x,y;
  111.             cin >> x >> y;
  112.             update(x,y,n);
  113.         }
  114.         else
  115.         {
  116.             int x1,x2,y1,y2;
  117.             cin >> x1 >> y1 >> x2 >> y2;
  118.             cout << query(x1,y1,x2,y2) << '\n';
  119.         }
  120.    }
  121.    return 0;
  122. }
  123.  
Success #stdin #stdout 0s 7540KB
comments (?)
stdin
copy 
4 3
.*..
*.**
**..
****
2 2 2 3 4
1 3 3
2 2 2 3 4
stdout
copy 
3
4
https://ideone.com/mcAdwL
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!