분할정복을 이용한 2D update, query 처리

$N*M$ 크기의 격자에 다음과 같은 두 쿼리가 주어진다.

1. 한 칸의 값을 바꾼다

2. (x1, y1) ~ (x2, y2) 의 합, 최댓값, 최솟값 등을 구한다.

 

이 문제는 1차원의 문제가 segment tree 를 이용하면 풀리듯이 2D Segment Tree 를 이용하면 풀 수 있다. 하지만 2D Segment Tree 를 사용하면 공간 복잡도가 다이나믹 세그 + 메모리 제한이 빡빡할 경우에는 경로 압축까지 해 주어야 $O(NlogN)$ 이 나오기 때문에 시간, 공간의 측면에서 모두 비효율 적이다.

 

하지만 이 문제가 오프라인으로 풀 수 있다면 2D Segment Tree 를 구현하지 않아도 더 빠르게 풀 수 있다. 바로 분할 정복을 이용한 것이다.

 

시간의 흐름에 따라 1, 2번 종류의 쿼리가 하나씩 들어올 것이다. 이 타임라인에 대한 분할정복을 생각해 보자.

기본적인 아이디어는 다음과 같다. 모든 질의 쿼리에 대하여 자신보다 앞에 나온 update 쿼리를 처리했다면 이 문제를 풀 수 있다. 이를 그냥 하면 $O(Q^2)$ 이니, 분할 정복을 이용하여 $O(QlogQ)$ 로 줄일 수 있다.

 

현재 시간의 구간이 [s, e] 이면 이를 [s, m], [m+1, e] 의 두 구간으로 쪼갤 수 있다. 

이 두 구간에 대하여 분할정복을 실시하자. update 쿼리를 i, question 쿼리를 j라고 생각하자.

1. i, j -> [s, m] : solve(s, m) 에서 이미 처리 되었다.

2. i, j -> [m+1, e] : solve(m+1, e) 에서 이미 처리 되었다.

3. i -> [m+1, e], j -> [s, m] : i가 j보다 시간상으로 나중에 일어났으므로, i는 j에게 영향을 미치지 못한다. 즉 고려할 필요가 없다.

4. i -> [s, m], j -> [m+1, e] : 이 경우만 생각하자.

 

정리 하자면, 지금 우리는 [m+1, e] 의 모든 question 쿼리들을 갱신해 주고자 한다. 이 갱신 값들은 [s, m] 의 update 에 의하여 일어난 변화들을 잘 조작해 주면 된다. 지금의 상황을 잘 살펴 보면, 이는 미리 모든 업데이트가 일어난 후, 쿼리가 들어오는 문제이다.

 

이는 x축을 쓸고 지나가면서 y축의 값들을 Segment Tree 에 관리해 주고, 모든 쿼리를 정렬한 후 Line Sweeping 을 통하여 풀 수 있다.

 

전체적인 과정은 : solve(s, e) 에 대하여

solve(s, m)

[s, m]의 업데이트를 이용하여 [m+1, e]의 question을 갱신

solve(m+1, e)

를 하면 된다.

 

예시 문제로는 KOI 2018 3번 조화행렬이 있다. 다음 코드는 조화행렬의 코드이다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int M, N, dp[MAXN+10], ans;
struct tup
{
    int a, b, c;
    bool operator < (const tup& p) { return a<p.a; }
};
tup A[MAXN+10];

struct BIT
{
    int tree[MAXN+10];
    BIT bit() { memset(tree, 0, sizeof(tree)); }
    void update(int i, int val) { for(; i<=N; i+=(i&-i)) tree[i]=max(tree[i], val); }
    int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret=max(ret, tree[i]); return ret; }
    void flush(int i) { for(; i<=N; i+=(i&-i)) tree[i]=0; }
};
BIT bit;

void solve(int s, int e)
{
    int i, j;
    if(s==e)
    {
        dp[s]=max(dp[s], 1);
        return;
    }

    int mid=s+e>>1;
    solve(s, mid);

    vector<tup> L, R;
    for(i=s; i<=mid; i++) L.push_back({A[i].b, A[i].c, dp[i]});
    for(i=mid+1; i<=e; i++) R.push_back({A[i].b, A[i].c, i});
    sort(L.begin(), L.end());
    sort(R.begin(), R.end());

    int pt=0;
    for(i=0; i<R.size(); i++)
    {
        while(pt<L.size() && L[pt].a<R[i].a) bit.update(L[pt].b, L[pt].c), pt++;
        dp[R[i].c]=max(dp[R[i].c], bit.query(R[i].b)+1);
    }
    for(i=0; i<L.size(); i++) bit.flush(L[i].b);

    solve(mid+1, e);
}

int main()
{
    int i, j;

    scanf("%d%d", &M, &N);

    vector<int> Vb, Vc;
    for(i=1; i<=N; i++) scanf("%d", &A[i].a);
    for(i=1; i<=N; i++) scanf("%d", &A[i].b), Vb.push_back(A[i].b);
    if(M==3) for(i=1; i<=N; i++) scanf("%d", &A[i].c), Vc.push_back(A[i].c);
    else for(i=1; i<=N; i++) A[i].c=A[i].a, Vc.push_back(A[i].c);

    sort(Vb.begin(), Vb.end());
    sort(Vc.begin(), Vc.end());

    for(i=1; i<=N; i++) A[i].b=lower_bound(Vb.begin(), Vb.end(), A[i].b)-Vb.begin()+1;
    for(i=1; i<=N; i++) A[i].c=lower_bound(Vc.begin(), Vc.end(), A[i].c)-Vc.begin()+1;

    sort(A+1, A+N+1);

    solve(1, N);
    for(i=1; i<=N; i++) ans=max(ans, dp[i]);
    printf("%d", ans);
}

 

또다른 예시 문제로, JOISC 2019 Examination 의 코드이다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

struct Data { int X, Y, Z, id; };

int N, Q, ans[MAXN+10];
pii A[MAXN+10];
Data B[MAXN+10];

struct Query { int x, y, num; };
vector<Query> todo;

vector<int> xcomp, ycomp;
int getxcomp(int x) { return lower_bound(xcomp.begin(), xcomp.end(), x)-xcomp.begin()+1; }
int getycomp(int y) { return lower_bound(ycomp.begin(), ycomp.end(), y)-ycomp.begin()+1; }

struct BIT
{
    int tree[MAXN+10];
    BIT() { memset(tree, 0, sizeof(tree)); }
    void update(int i) { for(; i<=ycomp.size(); i+=(i&-i)) tree[i]++; }
    int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
    void fflush(int i) { for(; i<=ycomp.size(); i+=(i&-i)) tree[i]=0; }
} bit;

void solve(int s, int e)
{
    int i, j;
    if(s+1==e) return;

    int mid=s+e>>1;
    solve(s, mid);

    vector<Query> a, b;
    for(i=s; i<mid; i++) if(todo[i].num==0) b.push_back(todo[i]);
    for(i=mid; i<e; i++) if(todo[i].num!=0) a.push_back(todo[i]);

    sort(a.begin(), a.end(), [&](const Query &p, const Query &q) { return p.x>q.x; });
    sort(b.begin(), b.end(), [&](const Query &p, const Query &q) { return p.x>q.x; });

    for(i=0, j=0; i<a.size(); i++)
    {
        for(; j<b.size() && b[j].x>=a[i].x; j++) bit.update(b[j].y);
        ans[a[i].num]+=bit.query(ycomp.size())-bit.query(a[i].y-1);
    }
    for(j=0; j<b.size(); j++) bit.fflush(b[j].y);
    solve(mid, e);
}

int main()
{
    int i, j;

    scanf("%d%d", &N, &Q);
    for(i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second), xcomp.push_back(A[i].first), ycomp.push_back(A[i].second);
    for(i=1; i<=Q; i++) scanf("%d%d%d", &B[i].X, &B[i].Y, &B[i].Z), B[i].id=i;

    sort(xcomp.begin(), xcomp.end()); xcomp.erase(unique(xcomp.begin(), xcomp.end()), xcomp.end());
    sort(ycomp.begin(), ycomp.end()); ycomp.erase(unique(ycomp.begin(), ycomp.end()), ycomp.end());

    sort(A+1, A+N+1, [&](const pii &p, const pii &q) { return p.first+p.second>q.first+q.second; });
    sort(B+1, B+Q+1, [&](const Data &p, const Data &q) { return p.Z>q.Z; });

    int it=1;
    for(i=1; i<=Q; i++)
    {
        for(; it<=N && A[it].first+A[it].second>=B[i].Z; it++) todo.push_back({getxcomp(A[it].first), getycomp(A[it].second), 0});
        todo.push_back({getxcomp(B[i].X), getycomp(B[i].Y), B[i].id});
    }

    solve(0, todo.size());
    for(i=1; i<=Q; i++) printf("%d\n", ans[i]);
}