BOJ 10717 성벽

성벽
(http://boj.kr/10717)

일본어 풀이가 있다.

왼쪽 위 꼭짓점을 기준으로 오른쪽 아래 꼭짓점을 찾는다고 생각해보자. 전체적으로 대각선 형태로 찾게 된다.
기준점에서 오른쪽 아래 점이 적어도 \(L-1\)만큼은 떨어져야 하고, 오른쪽으로 뻗어나갔을 때 최대 거리와 아래로 뻗어나갔을 때 최대 거리의 최솟값이 가능할만한 범위다.
다시말해 \([L-1~,\text{(뻗어나갈 수 있는 거리)}]\)가 확인해야할 범위다.

답이 되는 점들은 범위 안에 포함되는 점들 중에서 찾아야 한다.
이 점들은 왼쪽과 위로 뻗었을 때 최대 거리 중에 작은 것 만큼까지만 답이 될 수 있다.

그럼 이 점들을 찾는 시간을 줄여보자.
우선 상하좌우로 뻗는 거리는 DP로 구할 수 있다.
그리고 답을 찾을 때 범위 내의 합을 구하는 쿼리를 트리로 처리한다.
오른쪽 아래 점이 되는 점들은 어떤 시점(최대한 뻗어나갔을 때)이 지나면 항상 오른쪽 아래 점이 될 수 있다.
그러므로 이 시점을 저장해뒀다가 그 시점이 오면 트리(대각선)에 업데이트해준다.
그러면 매 점에서 자신이 왼쪽 위 점인 사각형은 트리를 사용해 구할 수 있게 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
bool mp[4001][4001];
int r[4001][4001], c[4001][4001], d[4001][4001], tree[8001][4001];
vector<pair<int, int> > upd[8001];
 
int main() {
    int h, w, l, p;
    scanf("%d %d %d %d", &h, &w, &l, &p);
    while (p--) {
        int u, v;
        scanf("%d %d", &u, &v);
        mp[u][v] = true;
    }
 
    for (int i = 1;i <= h;++i)
        for (int j = 1;j <= w;++j) {
            if (mp[i][j])
                r[i][j] = 0;
            else
                r[i][j] = r[i - 1][j] + 1;
        }
    for (int j = 1;j <= w;++j)
        for (int i = 1;i <= h;++i) {
            if (mp[i][j])
                c[i][j] = 0;
            else
                c[i][j] = c[i][j - 1] + 1;
        }
    for (int i = 1;i <= h;++i)
        for (int j = 1;j <= w;++j) {
            r[i][j] = min(r[i][j], c[i][j]);
            c[i][j] = 0;
        }
    for (int i = h;i >= 1;--i)
        for (int j = 1;j <= w;++j) {
            if (mp[i][j])
                c[i][j] = 0;
            else
                c[i][j] = c[i + 1][j] + 1;
        }
    for (int j = w;j >= 1;--j)
        for (int i = 1;i <= h;++i) {
            if (mp[i][j])
                d[i][j] = 0;
            else
                d[i][j] = d[i][j + 1] + 1;
        }
    for (int i = 1;i <= h;++i)
        for (int j = 1;j <= w;++j)
            c[i][j] = min(c[i][j], d[i][j]);
 
    for (int i = 1;i <= h;++i)
        for (int j = 1;j <= w;++j) 
            upd[i - j + 4000].push_back({ i - r[i][j] + 1, i });
    for (int i = 4001 - w;i <= 3999 + h;++i)
        sort(upd[i].begin(), upd[i].end(), greater<pair<int, int> >());
 
    long long ans = 0;
    for (int i = 1;i <= h;++i)
        for (int j = 1;j <= w;++j) {
            while (!upd[i - j + 4000].empty() && upd[i - j + 4000].back().first <= i) {
                for (int x = upd[i - j + 4000].back().second;x <= 4000;x += x & -x)
                    tree[i - j + 4000][x]++;
                upd[i - j + 4000].pop_back();
            }
            for (int x = max(i + l - 2, i + c[i][j]);x >= 1;x -= x & -x)
                ans += tree[i - j + 4000][x];
            for (int x = i + l - 2;x >= 1;x -= x & -x)
                ans -= tree[i - j + 4000][x];
        }
 
    printf("%lld", ans);
        
    return 0;
}