(1780) 종이의 개수

https://www.acmicpc.net/problem/1780

단계별로 풀어보기

24단계(분할 정복) 3번째

 

 

 

4등분 대신 9등분 하는 점만 빼면 이전 문제와 똑같다.

대신 가능한 값이 -1, 0, 1 세가지이므로 그대로 저장하면 누적합 테크닉을 이용할 수 없기 때문에 1 대신 가능한 최솟값의 절댓값보다 큰 값을 저장해야 한다. 그렇게 하지 않을 경우 구간이 전부 0이 아니여도 누적합이 0인 경우가 발생할 수 있다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define one 2188 // 3^7+1

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, a= 0, b= 0, c= 0;
  
  cin >> n;
  
  vector v(n+1, vector<int> (n+1));
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cin >> v[i][j];
      if(v[i][j]==1)  v[i][j]= one;
      v[i][j]+= v[i-1][j]+v[i][j-1]-v[i-1][j-1];
    }
  }
  
  auto func= [&](auto self, int x, int y, int l) -> void {
    int acc= v[x+l-1][y+l-1]-v[x-1][y+l-1]-v[x+l-1][y-1]+v[x-1][y-1];
    
    if(acc==-l*l){
      a++;
      return;
    }else if(acc==0){
      b++;
      return;
    }else if(acc==one*l*l){
      c++;
      return;
    }
    
    self(self, x, y, l/3);
    self(self, x, y+l/3, l/3);
    self(self, x, y+2*l/3, l/3);
    self(self, x+l/3, y, l/3);
    self(self, x+l/3, y+l/3, l/3);
    self(self, x+l/3, y+2*l/3, l/3);
    self(self, x+2*l/3, y, l/3);
    self(self, x+2*l/3, y+l/3, l/3);
    self(self, x+2*l/3, y+2*l/3, l/3);
  };
  
  func(func, 1, 1, n);
  
  cout << a << "\n" << b << "\n" << c;
  
  return 0;
}