fork download
  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
stdin
4 3
.*..
*.**
**..
****
2 2 2 3 4
1 3 3
2 2 2 3 4
stdout
3
4