codeforces #578 div2 D - White Lines ( 배열구간 연산 )
https://codeforces.com/contest/1200/problem/D W,B 둘중 하나로만 이루어진 n*n배열이 주어졌을 때, 단 한번 k*k크기의 구간을 W로 바꿀 수 있다면 W로 빙고가 이루어지는 경우의 최대값을 반환하는 문제이다. row따로 column따로 생각할 건데, row만 차례로 볼 때, i번째 row에서 B가 나타난다면 첫번째 위치를 L, 마지막 위치를 R이라고 하자. 이때, R-L+1 (i,j)를 기준으로 k*k 구간을 W로 바꿀때 추가되는 빙고의 수라고 할 것이다. 일단은 row와 column 따로따로 '[r1,c1] ~ (r2+1,c2+1)에 속하는 ac[i][j]의 값을 1 증가하라' 는 의미로 다음과 같이 전처리 한다. ac[r2 + 1][c2 + 1]++; //[0,..
2019. 11. 15.