[KOI 2018 본선] 조화로운 행렬 ★

문제 링크

Subtask: $M = 2, 3 ≤ N ≤ 10\,000$ (14점)

어차피 부분행렬 속 각 열 속의 등수가 전부 같은 것이 조건이므로,

행렬의 각 열의 순서는 바뀌어도 상관이 없다.

따라서 각 열을 첫번째 행의 크기 순서대로 정렬하는 것이 가능한데,

이러면 LIS 문제로 환원되어 쉽게 풀 수 있다.

$O(n^2)$으로도 가능한데, $O(n\log n)$으로 풀어 Subtask #3와 함께 긁었다.

Subtask: $M = 3, 3 ≤ N ≤ 10\,000$ (9점)

$O(n\log n)$의 LIS는 적용할 수 없다. 따라서 $O(n^2)$ LIS를 사용하여 풀 수 있다.

코드

Subtask: $M = 2, 3 ≤ N ≤ 2\cdot 10^5$ (15점)

세그트리를 이용한 $O(n\log n)$이 풀이의 확장에 더 도움이 되므로 세그트리로 짰다.

코드

Fulltask: $M = 3, 3 ≤ N ≤ 2\cdot 10^5$ (62점)

Solution 1

바로 이전에 썼던 JOISC 시험과 거의 동일하다.

CDQ 알고리즘을 이용하는 것인데, 다른 점이라면 합이 아닌 최댓값을 관리해야 된다는 것이다.

또한, 분할정복 과정에서 후위순회로 풀면 오른쪽 문제가 왼쪽에서 전이되는 값을 이어가지 못한다.

따라서 중위순회로 문제를 풀어줘야 한다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
void o_o(){ cerr << endl; }
template <class H, class...T> void o_o(H h,T...t) { cerr << ' ' << h; o_o(t...); }
#define debug(...) cerr<<'['<<#__VA_ARGS__<<"]:",o_o(__VA_ARGS__)
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define size(x) int((x).size())
#define fi first
#define se second
#define Mup(x,y) x = max(x,y)

const int N = 2e5+3;
int m, n;
struct P { int x, y, z, i; } q[N], p[N];
bool byX(P &a, P &b){ return a.x < b.x; }
bool byY(P &a, P &b){ return a.y < b.y; }
bool byZ(P &a, P &b){ return a.z < b.z; }

struct segment_tree {
    int t[2*N] {0,};
    void update(int k, int v) {
        k += N;
        for (t[k] = v; (k /= 2) >= 1;) {
            t[k] = max(t[2*k],t[2*k+1]);
        }
    }
    int query(int a, int b) {
        int r = 0;
        for (a += N, b += N; a <= b; ++a /= 2, --b /= 2) {
            if (a&1) r = max(r,t[a]);
            if (~b&1) r = max(r,t[b]);
        }
        return r;
    }
} ds;

void subtask1n3() {
    sort(q+1,q+n+1,byY);
    rep(i,1,n) q[i].y = i;
    sort(q+1,q+n+1,byX);
    rep(i,1,n) {
        int x = ds.query(1,q[i].y);
        ds.update(q[i].y,x+1);
    }
    cout << ds.query(1,n);
}

void solve(int lis[N], int a = 1, int b = n) {
    int m = (a+b)/2;
    if (a == b) { Mup(lis[m],1); return; }
    solve(lis,a,m);
    copy(q+a,q+b+1,p+a);
    sort(p+a,p+m+1,byY), sort(p+m+1,p+b+1,byY);
    {
        int i = a, j = m+1;
        while (i <= m or j <= b) {
            if (j > b or (i <= m and p[i].y < p[j].y)) {
                ds.update(p[i].z, lis[p[i].i]), ++i;
            } else if (i > m or (j <= b and p[i].y > p[j].y)) {
                Mup(lis[p[j].i], ds.query(1,p[j].z)+1), ++j;
            }
        }
    }
    rep(i,a,b) ds.update(p[i].z,0);
    solve(lis,m+1,b);
}

void subtask4() {
    sort(q+1,q+n+1,byZ);
    rep(i,1,n) q[i].z = i;
    sort(q+1,q+n+1,byX);
    rep(i,1,n) q[i].i = i;
    int lis[N] = {0,};
    solve(lis);
    cout << *max_element(lis,lis+n+1);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> m >> n;
    rep(i,1,n) cin >> q[i].x;
    rep(i,1,n) cin >> q[i].y;
    if (m == 2) subtask1n3();
    else {
        rep(i,1,n) cin >> q[i].z;
        subtask4();
    }
}

Solution 2

LIS 알고리즘을 일반화 시킨 풀이인데, 매우 흥미롭다.

길이가 $k$인 LIS의 체인을 관리하는 식의 문제가 된다.

구현은 해보지 않았고, 이 영상을 통해 잘 설명되어 있다.