Problem Solving Diary #12

BOJ 15844. Land of the Rainbow Gold

이런 식으로 연결 성분 개수를 특이한 그래프(여기서는 격자 그래프)에서 구하라고 하면 높은 확률로 오일러 지표를 쓰는 것이다. 흔히 아는 그 v-e+f 공식인데, 연결성분이 여러 개일 경우 공식이 조금 달라진다. 하여튼 v-e+f 형태로 나오는 것은 맞으니 외울 필요는 없고 그냥 여러 개 그려 보며 규칙을 찾으면 된다.

 

그래서 문제는 주어진 영역에서 v, e, f의 개수를 구하는 것이다. 일단 그래프는 각 격자칸을 점, 인접한 격자칸을 선으로 이은 형태가 되어야 할 것이다. 이렇게 하면 v, e, f를 어떻게 세어야 할 지 각이 잡힌다. 셋 모두 그 개수를 직접 세기보다는 빠지는 개수를 세서 여집합으로 처리하는 것이 편리할 것이다. 즉, 정점의 경우 그냥 체크를 하고, 간선의 경우 자신과 인접한 (최대 4개의) 간선들을 모두 체크를 한다. 이제 PST를 구현해서 온라인 2d query가 가능한 자료구조를 만들고, 적당히 구현하면 문제를 맞을 수 있다.

 

이렇게 하면 v, e는 쉽게 구해지는데, f를 구하는 게 쉽지 않다. 일단 맨 바깥의 면은 세지 않기로 하자. 이때 $v-e+f=(\text{연결성분 수})$가 성립한다. 그런데 막상 $f$를 구하려고 하면, $f$는 우리가 다루는 그래프에서 간선들 안으로 둘러싸인 부분의 개수인데, 이 크기가 꽤 크게 커질 수 있다. 강이 없다면 모두 $1 \times 1$ 정사각형 크기겠지만, 강이 있기 때문에 더 커질 수 있는 것이다. 예시로 강의 형태가 $S \times S$ 크기 정사각형 안의 모든 칸을 채우고 있다면, 그래프에서 찾는 '면'은 $(S+1) \times (S+1)$ 크기의 정사각형이 될 것이다. 그래서 v, e처럼 단순히 개수를 세는 등 단순한 방법으로는 처리가 안 된다.

 

여기서 문제의 유용한 조건을 활용해야 하는데, 바로 강을 이루는 칸이 모두 연결되어 있다는 성질이다. 따라서 원래대로라면 풀기 힘들었을 문제가 조금은 단순화된다. 어느 면에서 단순화되는가? 일단 용어 정의를 조금 명확하게 하고 가자.

• 현재 보고 있는 그래프는 각 칸을 정점으로, 각 칸별로 인접한 네 개의 칸에 대해 해당하는 정점들을 간선으로 이은 격자 그래프이다.
• 이때 강에 해당하는 칸은 정점을 만들지 않은 상태라고 생각해도 좋다.
• 이 그래프를 평면 그래프로 생각했을 때, 간선들로 인해 나누어지는 각각의 영역을 블럭이라고 하자. 

이때 아래 사실이 성립함을 알 수 있다.

• 강 칸들은 모두 같은 블럭 내부에 있다.
  • 증명) 자명. (여러 블럭 내에 있으면, 강 칸만을 이용해 한 블럭 내부에서 다른 블럭 내부로 갈 수 없음)

이 사실을 알게 되면, 다른 자명한 사실 하나가 끌려나온다. 어떤 블럭은 원래 넓이가 1이어야 하는데, 이 블럭의 넓이가 1보다 커질 이유는 단 하나, 강 칸의 존재밖에 없다. 또한 안에 강 칸이 존재하면 필연적으로 블럭의 넓이는 1보다 커진다. 따라서, 결론적으로 넓이가 1 이상인 블럭은 단 하나뿐이며, 그 블럭이 강 칸을 포함하는 블럭임을 알 수 있다.

 

우리가 알고자 하는 것은 주어진 영역 내에 있는 블럭의 개수이다. 블럭의 개수를 세기 위해서는, 처음에 강 칸이 없던 시절로 되돌아가서, 강 칸이 하나씩 추가될 때마다 블럭의 개수가 어떻게 변하는지를 세어 보는 것이 좋다. 다음과 같은 경우는 쉽게 처리된다.

• 모든 강 칸이 토지 밖에 있는 경우
  • 애초에 답이 무조건 1이라 논할 가치가 없다.
• 모든 강 칸이 토지 안에 있으면서, 토지의 경계 위에 있지 않은 경우 (강 칸이 토지 바깥으로부터 적어도 한 칸을 사이에 두고 있는 경우)
  • v, e 하듯이 f를 비슷한 방식으로 구해 준다. 이웃한 (최대 4개의) 1*1 크기 면을 체크해 주면 된다. 이렇게 하면 세어지지 않는 블럭이 딱 하나, 강 칸을 포함하는 블럭인데, 그것만을 더해주면 된다.
• 위 두 경우가 아닌 경우
  • 일단 v, e 하듯이 f를 비슷한 방식으로 구해 준다. 이렇게 하면 세어지지 않는 블럭이 딱 하나, 강 칸을 포함하지 않는 블럭뿐인데, 사실 이 블럭은 영역 바깥쪽과 인접해 있으므로 면으로 세어 줄 이유가 없다. 따라서 얘를 안 더하고 답을 구하면 된다.

#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct PST{
    struct Node{
        Node *lc, *rc;
        int sum;

        Node(int l, int r){
            sum = 0;
            if(l==r) lc = rc = nullptr;
            else{
                int m = (l+r)/2;
                lc = new Node(l, m);
                rc = new Node(m+1, r);
            }
        }

        Node(Node *lc, Node *rc, int sum): lc(lc), rc(rc), sum(sum){}

        ~Node(){
            if(lc) delete lc;
            if(rc) delete rc;
        }

        int query(int l, int r, int s, int e){
            if(r<s || e<l) return 0;
            if(s<=l && r<=e) return sum;
            int m = (l+r)>>1;
            return lc->query(l, m, s, e) + rc->query(m+1, r, s, e);
        }

        Node* update(int l, int r, int x, int v){
            if(l==r){
                Node* tmp = new Node(lc, rc, sum + v);
                return tmp;
            }
            int m = (l+r)>>1;
            Node* tmp = new Node(lc, rc, sum+v);
            if(x<=m) tmp->lc = lc->update(l, m, x, v);
            else     tmp->rc = rc->update(m+1, r, x, v);
            return tmp;
        }
    } *root = nullptr;
    int n;

    PST(){}
    Node *yHistory[200002];
    int yMaximum;

    void init(int _n){
        n = _n;
        root = new Node(0, n);
        for(int i=0; i<=200001; i++) yHistory[i] = nullptr;
        yMaximum = 0;
    }

    void update(int x, int y){
        while(yMaximum < y) yHistory[yMaximum++] = root;
        root = root->update(0, n, x, 1);
    }

    void finish(){
        while(yMaximum < 200001) yHistory[yMaximum++] = root;
    }

    int query(int xl, int xr, int yl, int yr){
//        printf("(%d - %d) = %d\n", yHistory[yr]->query(0, n, xl, xr), (yl == 0 ? 0 : yHistory[yl-1]->query(0, n, xl, xr)));
        return yHistory[yr]->query(0, n, xl, xr) - (yl == 0 ? 0 : yHistory[yl-1]->query(0, n, xl, xr));
    }
} vpst, ehpst, evpst, fpst;

struct Point{
    int x, y;
    Point(){}
    Point(int x, int y): x(x), y(y){}
    bool operator<(const Point &r)const{
        if(y!=r.y) return y<r.y;
        return x<r.x;
    }
    bool operator==(const Point &r)const{
        return x==r.x && y==r.y;
    }
};

int N, M;
int xMin = 1e9, xMax = -1e9, yMin = 1e9, yMax = -1e9;
vector<Point> vvec, ehvec, evvec, fvec;

void check(int X, int Y){
    xMin = min(xMin, X), yMin = min(yMin, Y);
    xMax = max(xMax, X), yMax = max(yMax, Y);

    vvec.push_back(Point(X, Y));

    if(Y!=1) ehvec.push_back(Point(X, Y-1));
    if(Y!=M) ehvec.push_back(Point(X, Y));

    if(X!=1) evvec.push_back(Point(X-1, Y));
    if(X!=N) evvec.push_back(Point(X, Y));

    if(Y!=1 && X!=1) fvec.push_back(Point(X-1, Y-1));
    if(Y!=M && X!=1) fvec.push_back(Point(X-1, Y));
    if(Y!=1 && X!=N) fvec.push_back(Point(X, Y-1));
    if(Y!=M && X!=N) fvec.push_back(Point(X, Y));
}

void update(PST &pst, vector<Point> &vec){
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    pst.init(N);
    for(Point p: vec){
        pst.update(p.x, p.y);
    }
    pst.finish();
}

void init(int R, int C, int sr, int sc, int K, char *S){
    N = R, M = C;
    vpst.init(N);
    ehpst.init(N);
    evpst.init(N);
    fpst.init(N);

    int x = sr, y = sc;
    check(x, y);
    for(int i=0; i<K; i++){
        if(S[i] == 'N') x--;
        else if(S[i] == 'E') y++;
        else if(S[i] == 'W') y--;
        else x++;
        check(x, y);
    }

    update(vpst, vvec);
    update(ehpst, ehvec);
    update(evpst, evvec);
    update(fpst, fvec);
}

int colour(int x1, int y1, int x2, int y2){
    ll V = ll(x2-x1+1) * ll(y2-y1+1) - vpst.query(x1, x2, y1, y2);
    ll EH = ll(x2-x1+1) * ll(y2-y1) - ehpst.query(x1, x2, y1, y2-1);
    ll EV = ll(x2-x1) * ll(y2-y1+1) - evpst.query(x1, x2-1, y1, y2);
    ll F = ll(x2-x1) * ll(y2-y1) - fpst.query(x1, x2-1, y1, y2-1);

    if(x1 < xMin && xMax < x2 && y1 < yMin && yMax < y2) F++;

//    printf("%lld %lld %lld %lld\n", V, EH, EV, F);

    return V-(EH+EV)+F;
}

BOJ 17635. Bridges

이 문제는 제한이 매우 특이하다. 5만~10만 정도의 제한이면 보통 무거운 로그제곱 ~ 로그세제곱 아니면 루트를 생각해볼 수 있다. 그런데 로그가 무거운 거였으면 보통 TL을 늘리지 N을 줄이지는 않는다. 그래서 루트로 접근해봄직 하다.

 

단순 루트는 어려운데, 그래프에서 루트로 기준을 잡기는 참 어렵다. 잘해봐야 차수로 접근하는 정도이다. 차수 접근은 잘 먹히지 않으니, 다른 방법을 찾아보자. 쿼리를 인접한 쿼리 $B$개씩 묶어서 $B \sim \sqrt{Q}$ 정도가 되게 하면 적당할 것 같다.

 

이렇게 쿼리를 묶고 나면, 이제 한 쿼리 묶음을 어떻게 빠르게 처리할 지 생각해 보자. 일단 문제의 형태를 보았을 때, MST를 이용하는 것이 적당해 보인다. 주어진 그래프를 MST로 압축해도 답이 변하지 않기 때문이다. 이는 MST가 형성되는 과정에서, $d$ 이하의 가중치 간선만으로 이동할 수 있는 컴포넌트가 MST에서도 변하지 않음을 생각하면 된다. 다만 이 경우에는 가중치가 큰 간선부터 선택해 줘야 한다는 사소한 차이는 있다.

 

그러나 이 MST 아이디어는 이렇게 업데이트 쿼리가 들어오면 쉽지 않은데, 일단 쿼리를 루트 개씩 쪼갰으니, 이 쿼리 묶음에서는 거의 모든 간선, 정확히는 $M - \sqrt {Q}$개 정도의 간선이 고정이라는 것이다. 이들만을 이용해서라도 미리 MST를 만들어 놓으면 조금 편해진다.

 

추가로, 인접한 루트 개의 쿼리 중에서 질문 쿼리를 보자. 질문 쿼리에 등장하는 가중치는 루트 개 이하인데, 따라서 나머지 모든 간선의 가중치를 루트 개로 제한해 생각해도 된다. 초반에 전처리할 때 좌표 압축을 하고 시작하면 나중에 상수를 줄일 수 있다. 루트 로그로 푸는 문제 특성상 어떻게든 상수를 줄여야 하기 때문에 꽤 중요하다.

 

이제 루트 개의 가중치 상황 각각에 대해서 생각해 보자. 현재 가진 것은 쿼리 묶음 밖에 있는 간선들로 이루어진 MST (포레스트)와 추가 간선 (간선 블럭에 포함된) 여러 개이다. 이번 쿼리에 해당하는 가중치가 $w$라고 하자. 이때 MST에서 $w$ 이상 가중치의 간선만 묶었을 때 생기는 component 들이 있을 것이다. 이들은 당연히 일종의 forest를 이룬다. 일단 이것을 미리 구해놓을 수 있다. 시간 복잡도는 나중에 생각하기로 하자. 그리고, 가중치가 $w$ 이상인 추가 간선들을 보며 갈 수 있는 정점의 수를 최종적으로 계산한다.

 

이제 그 자세한 과정을 들여다보자. 먼저 쿼리 블럭을 나눈다. 각 쿼리 블럭에 대해 가중치를 renumbering 해 준다. 이후부터는 가중치가 큰 쿼리와 간선부터 볼 것이다. 가중치가 큰 간선이 나오면 양쪽 점을 union find로 이어 준다. 가중치가 큰 쿼리가 나오면 사용할 수 있는 예비 간선 목록을 살펴보며, 가중치가 적당히 크면 모두 이어 준 다음, 답을 계산하고 다시 rollback 해준다.

 

이 전체 과정의 시간 복잡도는 $O(Q \sqrt {Q} \log {Q}$ 정도이며, 상수를 매우 작게 짜야 통과된다. 다음은 구현할 때 참고할 만한 최적화이다.

• STL 스택보다 벡터가 빠르다. (기본 상식으로 알아두자)
• 루트질을 할 때는 버킷(묶음)의 크기를 sqrt(N) 같이 계산하지 말고, 입력 제한을 보고 적당한 상수로 결정하는 것이 좋다. (역시 기본 상식으로 알아두자)
• 쿼리의 시점에서 간선 가중치를 판별하는 로직을 잘 짜야 한다. 간선 가중치가 한 쿼리 구간 내에서 여러 번 바뀔 수 있기 때문이다. 이분 탐색을 하면 로그가 붙기 때문에 별로 추천하지 않는다. 그보다는 예비 간선의 수도 루트 개 이하이고, 쿼리 시점도 루트 개 이하라는 점을 이용해 크기 Q의 행렬을 만들어 관리해 보자. 이렇게 할 경우 루트가 붙지 않는다. 이 배열은 매 구간마다 초기화할 필요가 없다는 것이 장점이다.
• 정렬은 전처리 때 할 수 있으면 최대한 미리 해 두자.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int G = 320;

struct UnionFind{
    int n;
    int par[50002], sz[50002];
    vector<pair<int, int> > stk;

    void init(int _n){
        n = _n;
        for(int i=1; i<=n; i++) par[i] = i, sz[i] = 1;
        stk.clear();
    }

    int find(int x){
        if(par[x] == x) return x;
        return find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        if(x==y) return;
        if(sz[x] > sz[y]) swap(x, y);
        stk.push_back(make_pair(-y, sz[y]));
        stk.push_back(make_pair(x, par[x]));
        par[x] = y;
        sz[y] += sz[x];
    }

    void rollback(){
        while(!stk.empty()){
            auto p = stk.back();
            stk.pop_back();
            if(p.first < 0) sz[-p.first] = p.second;
            else            par[p.first] = p.second;
        }
    }

    void check(){
        stk.clear();
    }
} dsu;

struct Edge{
    int x, y, w, idx;
    Edge(int x, int y, int w, int idx): x(x), y(y), w(w), idx(idx){}
    bool operator<(const Edge &r)const{
        return w>r.w;
    }
};

int n, m, q;
vector<Edge> edgeVec;
int ex[100002], ey[100002], weight[100002];
int qt[100002], qa[100002], qb[100002];
int ans[100002];

void solve(int L, int R);

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        int x, y, w;
        scanf("%d %d %d", &x, &y, &w);
        ex[i] = x, ey[i] = y, weight[i] = w;
        edgeVec.push_back(Edge(x, y, w, i));
    }
    sort(edgeVec.begin(), edgeVec.end());

    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        scanf("%d %d %d", &qt[i], &qa[i], &qb[i]);
    }

    for(int d=1; d<=q; d+=G){
        solve(d, min(q, d+G-1));
    }
    for(int i=1; i<=q; i++) if(qt[i]==2) printf("%d\n", ans[i]);
}

bool edgeUsed[100002];

struct dat{
    int x, w, idx;
    dat(){}
    dat(int x, int w, int idx): x(x), w(w), idx(idx){}
    bool operator<(const dat &r)const{
        return w>r.w;
    }
};

int edgeIdx[100002];
int matrix[500][500]; /// matrix[i][j]: i번 간선의 쿼리 시점 j에서의 가중치
vector<int> usedEdges;
int S;

void solve(int L, int R){ /// L~R번 쿼리를 처리
    for(auto &p: edgeVec) p.w = weight[p.idx];
    sort(edgeVec.begin(), edgeVec.end());

    vector<dat> queryVec;
    usedEdges.clear();
    for(int i=L; i<=R; i++){
        if(qt[i] == 1) edgeUsed[qa[i]] = 1, usedEdges.push_back(qa[i]);
        else queryVec.push_back(dat(qa[i], qb[i], i));
    }
    sort(queryVec.begin(), queryVec.end());

    dsu.init(n);

    /// matrix를 채우고 각 시점에서 가중치에 대한 정보를 얻자
    sort(usedEdges.begin(), usedEdges.end());
    usedEdges.erase(unique(usedEdges.begin(), usedEdges.end()), usedEdges.end());
    S = (int)usedEdges.size();

    for(int i=0; i<S; i++){
        int x = usedEdges[i];
        edgeIdx[x] = i;
        matrix[i][0] = weight[x];
        for(int j=L; j<=R; j++){
            if(qt[j] == 1 && qa[j] == x) matrix[i][j-L] = qb[j];
            else if(j>L) matrix[i][j-L] = matrix[i][j-L-1];
        }
    }

    int pnt = 0;
    for(dat p: queryVec){
        while(pnt < (int)edgeVec.size() && edgeVec[pnt].w >= p.w){
            if(!edgeUsed[edgeVec[pnt].idx]) dsu.merge(edgeVec[pnt].x, edgeVec[pnt].y);
            pnt++;
        }
        dsu.check();

        for(int e: usedEdges){
            if(matrix[edgeIdx[e]][p.idx-L] < p.w) continue;
            dsu.merge(ex[e], ey[e]);
        }
        ans[p.idx] = dsu.sz[dsu.find(p.x)];

        dsu.rollback();
    }

    /// weight 배열 업데이트
    for(int i=L; i<=R; i++) if(qt[i] == 1) weight[qa[i]] = qb[i], edgeUsed[qa[i]] = 0;
}

BOJ 12735. Boat

입력에서 $A_i, B_i$로 등장하는 모든 수들을 좌표 압축 해서 오름차순으로 배열 $A_1, A_2, \cdots, A_k$라고 하자.

 

$DP[i][j]$: $i$번 학교가 (보트를 내보내는 학교들 중) A_{j-1}명 초과 A_{j}명 이하의 보트를 내보내는 가장 번호가 큰 학교일 때, $1$번 이상 $i$번 이하의 번호를 가진 학교가 보트를 내보내는 경우의 수

 

로 정의하자. $DP[i][x]$에서 $DP[j][y]$로 전이하는 경우를 보면, $i < k \le j$인 $k$에 대해서 $k$번 학교가 $A_{y-1}$ 초과 $A_y$ 개 이하의 보트를 내보내지 못하는 경우는 내보낼 수 없다. 이 개수는 쉽게 셀 수 있으므로 제외하고, 남은 학교들, 즉 이 범위 내의 보트를 내보낼 수 있는 학교의 개수를 세어서 이 수를 $X$라고 하자. 또 $A_y - A_{y-1}$을 $Y$라고 하자. 이때, 우리는 다음과 같은 경우의 수를 세어야 한다.

 

• 길이가 $X$이고 모든 수가 $0$ 이상 $Y$ 이하인 정수이며, $0$이 아닌 수들만 보면 오름차순인 수열의 개수 (단, $A_X \neq Y$)

위 점화식은 식정리를 조금 해 보면 $O(N^3)$에 충분히 전처리가 가능하다는 것을 알 수 있다. 따라서 총 문제도 $O(N^3)$에 풀 수 있다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

ll mpow(ll x, ll y){
    if(!y) return 1;
    if(y%2) return mpow(x, y-1) * x % MOD;
    ll tmp = mpow(x, y/2);
    return tmp * tmp % MOD;
}

ll modInv(ll x){
    return mpow(x, MOD-2);
}

int n, k;
ll a[502], b[502];
ll arr[1002];

void input();
void init();
void solve();
void output();

int main(){
    input();
    init();
    solve();
    output();
}

void input(){
    vector<int> vec;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld", &a[i], &b[i]);
        a[i]--;
        vec.push_back(a[i]);
        vec.push_back(b[i]);
    }
    vec.push_back(0);
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    k = (int)vec.size() - 1;
    for(int i=0; i<=k; i++) arr[i] = vec[i];

    for(int i=1; i<=n; i++){
        a[i] = lower_bound(arr, arr+k+1, a[i]) - arr + 1;
        b[i] = lower_bound(arr, arr+k+1, b[i]) - arr;
    }
}

ll nCk[502][502];
ll xCi[1002][502];
ll xySum[1002][502];

void init(){
    /// nCk
    for(int i=0; i<=n; i++){
        nCk[i][0] = nCk[i][i] = 1;
        for(int j=1; j<i; j++){
            nCk[i][j] = (nCk[i-1][j] + nCk[i-1][j-1]) % MOD;
        }
    }

    /// xCi
    for(int i=1; i<=k; i++){
        ll X = arr[i] - arr[i-1];
        xCi[i][1] = X;
        for(int j=2; j<=n; j++){
            xCi[i][j] = xCi[i][j-1] * (X-j+1) % MOD * modInv(j) % MOD;
        }
    }

    /// xyMult
    for(int i=1; i<=k; i++){
        for(int j=1; j<=n; j++){
            for(int d=1; d<=j; d++){
                xySum[i][j] = (xySum[i][j] + xCi[i][d] * nCk[j-1][d-1]) % MOD;
            }
        }
    }
}

int sum[502][1002];
ll DP[502][1002];
ll DPsum[502][1002];

void solve(){
    /// sum
    for(int i=1; i<=n; i++){
        for(int j=a[i]; j<=b[i]; j++){
            sum[i][j] = 1;
        }
    }
    for(int j=1; j<=k; j++) for(int i=1; i<=n; i++) sum[i][j] += sum[i-1][j];

    DP[0][0] = 1;
    for(int i=0; i<=k; i++) DPsum[0][i] = 1;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            if(j < a[i] || b[i] < j) continue;
            for(int prv=0; prv<i; prv++){
                DP[i][j] = (DP[i][j] + DPsum[prv][j-1] * xySum[j][sum[i][j]-sum[prv][j]]) % MOD;
            }
        }

        for(int j=1; j<=k; j++) DPsum[i][j] = (DPsum[i][j-1] + DP[i][j]) % MOD;

//        for(int j=1; j<=k; j++) printf("%lld ", DP[i][j]);
//        puts("");
    }
}

ll ans;

void output(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            ans = (ans + DP[i][j]) % MOD;
        }
    }

    printf("%lld", ans);
}