티스토리 뷰
반응형
1. DP[i][j] = (i, j)가 오른쪽 밑 모서리인 정사각형의 최대 크기
1-(1). (i,j) 가 0인 경우 -> DP[i][j]=0;
1-(2). (i,j) 가 1인 경우 -> min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
2. parametric search
3. 쿼리의 정답이 특정 값 mid 이상인지 여부는 DP 배열을 소스로 만든 sparse table을 통해 바로 알 수 있음.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | // code by RiKang, weeklyps.com #include <stdio.h> #include <algorithm> #include <vector> using namespace std; typedef short node_type; namespace MIN_ver{ node_type INIT = 1000000000; node_type node_calc(node_type n1, node_type n2){return min(n1,n2);} } namespace MAX_ver{ node_type INIT = 0; node_type node_calc(node_type n1, node_type n2){return max(n1,n2);} } using namespace MAX_ver; const int N = 1005, log_N = 11, M = 1005, log_M = 11; struct sparse_table{ // 0-based int n1,m1; node_type T[N][M][log_N][log_M]; node_type res[N][M]; // res : 기존 배열 int cal_d[N+M]; void init(int n2,int m2){ n1=n2,m1=m2; for(int i=1; i<N+M; i++){ cal_d[i] = cal_d[i-1]; while((1<<cal_d[i])<=i) cal_d[i]++; cal_d[i]--; } for(int i=0; i<n1; i++) for(int j=0; j<m1; j++) T[i][j][0][0] = res[i][j]; for(int di=0; di<log_N; di++){ if(di==0){ for(int dj=1; dj<log_M; dj++) for(int i=0; i<n1; i++) for(int j=0; j+(1<<dj)<=m1; j++) T[i][j][di][dj] = node_calc(T[i][j][di][dj-1], T[i][j+(1<<(dj-1))][di][dj-1]); } else{ for(int dj=0; dj<log_M; dj++) for(int i=0; i+(1<<di)<=n1; i++) for(int j=0; j+(1<<dj)<=m1; j++) T[i][j][di][dj] = node_calc(T[i][j][di-1][dj], T[i+(1<<di-1)][j][di-1][dj]); } } } node_type query(int x1, int y1,int x2, int y2){ if(x1>x2 || y1>y2) return INIT; int d1 = cal_d[x2-x1+1]; int d2 = cal_d[y2-y1+1]; int x3 = x2-(1<<d1)+1; int y3 = y2-(1<<d2)+1; node_type ret = T[x1][y1][d1][d2]; ret = node_calc(ret, T[x1][y3][d1][d2]); ret = node_calc(ret, T[x3][y1][d1][d2]); ret = node_calc(ret, T[x3][y3][d1][d2]); return ret; } }table; int n,m; int a[N][N]; int sum[N][N]; bool chk(int x1,int y1,int x2,int y2){ return (x2-x1+1)*(y2-y1+1) == sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]; } int main(){ scanf("%d %d",&n,&m); for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ scanf("%d",&a[i][j]); sum[i][j] = a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; } } for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ table.res[i][j] = 0; for(int k=i-table.res[i-1][j-1]; k<=i; k++){ if(chk(k,j-(i-k),i,j)){ table.res[i][j] = i-k+1; break; } } } } table.init(n+1,m+1); int t; scanf("%d",&t); while(t--){ int x1,y1,x2,y2; scanf("%d %d %d %d",&x1,&y1,&x2,&y2); int l = 0; int r = min(x2-x1+1, y2-y1+1)+1; while(l+1<r){ int mid = (l+r)/2; if(table.query(x1+mid-1,y1+mid-1,x2,y2)<mid) r = mid; else l = mid; } printf("%d\n",l); } return 0; } | cs |
반응형
'문제 풀이' 카테고리의 다른 글
[BOJ 13548] 수열과 쿼리 6 (0) | 2017.11.11 |
---|---|
[BOJ 13518] 트리와 쿼리 9 (0) | 2017.11.03 |
[BOJ 4008] 특공대 (0) | 2017.10.31 |
[CF 146 B] Let's Play Osu! (0) | 2017.10.31 |
[BOJ 2533] 사회망 서비스 (0) | 2017.10.31 |