XOR Sorting

Easy Version

각 인덱스를 정점으로 생각하고, 두 인덱스 $i, j$ 를 가중치가 $i \oplus j$ 인 간선으로 이어줍시다.

두 인덱스 $i$ , $j$ 가 같은 연결 요소 내에 있다면 두 원소의 위치를 바꿀 수 있습니다.

이제 문제를 가중치가 $k$ 이하인 간선만으로 정렬 가능하도록 하는 가장 작은 $k$ 를 구하는 문제로 바꿀 수 있습니다.

먼저 가중치가 $1$ 인 간선만 고려해 봅시다.

연결 요소를 괄호로 묶어서 표시하면 다음과 같습니다.

$(0, 1), (2, 3), (4, 5), (6, 7), \dots$

여기에 가중치가 $2$ 인 간선을 추가해 봅시다.

$(0, 1, 2, 3), (4, 5, 6, 7), \dots$

모든 연결 요소의 크기가 $2$ 에서 $4$ 로 두배가 되었습니다. 일단 계속해 봅시다.

가중치가 $3$ 인 간선을 추가해 봅시다.

$(0, 1, 2, 3), (4, 5, 6, 7), \dots$

$3$ 은 $1$ 과 $2$ 를 더해서 구성할 수 있으므로, 따로 나눠서 이동하면 되기에 영향을 주지 않습니다.

이제 가중치가 $4$ 인 간선을 추가해 봅시다.

$(0, 1, 2, 3, 4, 5, 6, 7), \dots$

또 연결 요소의 크기가 $4$ 에서 $8$ 로 두배가 되었습니다.

아까 $3$ 을 $1$ 과 $2$ 를 통해서 구성가능했던 것과 비슷하게 $5$ 부터 $7$ 까지 모두 $1$ , $2$ , $4$ 로 구성가능하다는 것을 알 수 있습니다.

이는 이진수 표현을 떠올리면 보다 쉽게 알 수 있습니다. $1$ , $2$ , $4$ 는 각각 서로 다른 최하위 $3$ 개의 비트를 나타내니까요.

따라서 간선의 가중치가 $2$ 의 거듭제곱이 아닌 경우 그보다 작은 가중치의 간선만으로도 똑같이 swap할 수 있으므로 $f(a)$ 는 항상 $2$ 의 거듭제곱입니다.

가중치가 $2^t$ 인 간선은 항상 $t$ 번째 비트가 $0$ 인 것과 그렇지 않은 것을 잇습니다.

맨 앞에서부터 $t$ 번째 비트가 $0$ 인 것과 아닌 것은 $2^t$ 개씩 번갈아가면서 나타납니다.

비트가 $0$ 인 것에 $2^t$ 를 더하거나 $1$ 인 것에 $2^t$ 를 빼서 이어지므로 앞에서부터 $2^{t + 1}$ 개씩 한 연결 요소가 됩니다.

$i$ 번째 연결 요소 속 최솟값을 $m_i$ , 최댓값을 $M_i$ 라 합시다.

만약 $M_i > m_{i + 1}$ 이라면 $i + 1$ 번째 연결 요소에 $i$ 번째 연결 요소보다 작은 원소가 항상 있게 되므로 정렬이 불가능합니다. ( $A \Rightarrow B$ )

만약 그러한 $i$ 가 존재하지 않는다면 각 연결요소는 모두 정렬가능하고, 연결요소가 만나는 부분끼리 정렬되어 있으므로( $M_i \leq m_{i + 1}$ ) 전체 정렬이 가능합니다. ( $\lnot A \Rightarrow \lnot B$ )

따라서 $M_i > m_{i + 1}$ 인 $i$ 의 존재는 정렬 불가능과 동치입니다.

이를 이용하면 어떤 $k$ 에 대해 정렬 불가능을 $O(n)$ 에 판단할 수 있습니다.

$f(a)$ 의 후보로 $2$ 의 거듭제곱만 살펴봐도 충분하므로 $\lfloor \log n \rfloor$ 개의 $k$ 만 살펴봐도 됩니다.

따라서 $O(n\log n)$ 에 문제를 해결할 수 있습니다.

코드 (C++)

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n, q;
    cin >> n >> q;
 
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
 
    if (is_sorted(a.begin(), a.end())) {
        cout << 0 << '\n';
        return;
    }
 
    int ans = n;
    for (int k = 1; k < n; k <<= 1) {
        int prevMax = -1;
        bool sortable = true;
 
        for (int i = 0; i < n; i += 2 * k) {
            int minValue = a[i], maxValue = a[i];
 
            for (int j = i + 1; j < min(n, i + 2 * k); j++) {
                minValue = min(minValue, a[j]);
                maxValue = max(maxValue, a[j]);
            }
 
            if (prevMax > minValue) {
                sortable = false;
                break;
            }
 
            prevMax = maxValue;
        }
 
        if (sortable) {
            ans = k;
            break;
        }
    }
 
    cout << ans << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
 
    while (t--) solve();
 
    return 0;
}

Hard Version

크기가 $2^t$ 인 블록은 $2^{t - 1}$ 인 블록 두개로 나눠서 생각할 수 있습니다.

만약 왼쪽 블록의 최댓값이 오른쪽 블록의 최솟값보다 작거나 같다면 $2^t$ 부분 전체를 정렬하기 위한 최소 $k$ 는 왼쪽 블록과 오른쪽 블록을 각각 정렬하기 위한 최소 $k$ 중 최댓값이 되고, 그렇지 않다면 배열 크기의 절반인 $2^{t - 1}$ 가 됩니다.

해당 방법을 통해 전체 배열을 정렬하기 위한 최소 $k$ 를 재귀적으로 구할 수 있습니다.

쿼리가 들어오면 $i$ 가 포함된 부분배열에 대해서만 위 값을 다시 계산해주면 답을 구할 수 있습니다.

배열은 자식 배열 두 개로 나눠지므로 갱신해야 할 부분 배열의 개수는 $\log n$ 개입니다.

이는 세그먼트 트리를 이용해서 구현할 수 있습니다.

따라서 시간 복잡도 $O(n + q\log n)$ 에 해결할 수 있습니다.

코드 (C++)

#include <bits/stdc++.h>
using namespace std;
 
constexpr int INF = 2e9;
 
struct SegmentTree {
    struct Node {
        int minValue, maxValue;
        int minK;
    };
 
    vector<Node> tree;
 
    SegmentTree(int n) {
        int height = 33 - __builtin_clz(n - 1);
        tree.assign(1 << height, {INF, INF, 0});
    }
 
    void change(int node, int start, int end, int index, int value) {
        if (start == end) {
            tree[node] = {value, value, 0};
            return;
        }
 
        int mid = (start + end) / 2;
        if (index <= mid) change(node << 1, start, mid, index, value);
        else change(node << 1 | 1, mid + 1, end, index, value);
 
        if (tree[node << 1].maxValue > tree[node << 1 | 1].minValue)
            tree[node].minK = (end - start + 1) / 2;
        else tree[node].minK = max(tree[node << 1].minK, tree[node << 1 | 1].minK);
 
        tree[node].minValue = min(tree[node << 1].minValue, tree[node << 1 | 1].minValue);
        tree[node].maxValue = max(tree[node << 1].maxValue, tree[node << 1 | 1].maxValue);
    }
};
 
void solve() {
    int n, q;
    cin >> n >> q;
 
    int paddedN = (n > 1 ? 1 << (32 - __builtin_clz(n - 1)) : 2);
 
    SegmentTree seg(paddedN);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
 
        seg.change(1, 0, paddedN - 1, i, a);
    }
 
    cout << seg.tree[1].minK << '\n';
 
    while (q--) {
        int i, x;
        cin >> i >> x;
 
        seg.change(1, 0, paddedN - 1, i, x);
 
        cout << seg.tree[1].minK << '\n';
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
 
    while (t--) solve();
 
    return 0;
}

Easy Version

각 인덱스를 정점으로 생각하고, 두 인덱스 $i, j$ 를 가중치가 $i \oplus j$ 인 간선으로 이어줍시다.

두 인덱스 $i$ , $j$ 가 같은 연결 요소 내에 있다면 두 원소의 위치를 바꿀 수 있습니다.

이제 문제를 가중치가 $k$ 이하인 간선만으로 정렬 가능하도록 하는 가장 작은 $k$ 를 구하는 문제로 바꿀 수 있습니다.

먼저 가중치가 $1$ 인 간선만 고려해 봅시다.

연결 요소를 괄호로 묶어서 표시하면 다음과 같습니다.

$(0, 1), (2, 3), (4, 5), (6, 7), \dots$

여기에 가중치가 $2$ 인 간선을 추가해 봅시다.

$(0, 1, 2, 3), (4, 5, 6, 7), \dots$

모든 연결 요소의 크기가 $2$ 에서 $4$ 로 두배가 되었습니다. 일단 계속해 봅시다.

가중치가 $3$ 인 간선을 추가해 봅시다.

$(0, 1, 2, 3), (4, 5, 6, 7), \dots$

$3$ 은 $1$ 과 $2$ 를 더해서 구성할 수 있으므로, 따로 나눠서 이동하면 되기에 영향을 주지 않습니다.

이제 가중치가 $4$ 인 간선을 추가해 봅시다.

$(0, 1, 2, 3, 4, 5, 6, 7), \dots$

또 연결 요소의 크기가 $4$ 에서 $8$ 로 두배가 되었습니다.

아까 $3$ 을 $1$ 과 $2$ 를 통해서 구성가능했던 것과 비슷하게 $5$ 부터 $7$ 까지 모두 $1$ , $2$ , $4$ 로 구성가능하다는 것을 알 수 있습니다.

이는 이진수 표현을 떠올리면 보다 쉽게 알 수 있습니다. $1$ , $2$ , $4$ 는 각각 서로 다른 최하위 $3$ 개의 비트를 나타내니까요.

가중치가 $2^t$ 인 간선은 항상 $t$ 번째 비트가 $0$ 인 것과 그렇지 않은 것을 잇습니다.

맨 앞에서부터 $t$ 번째 비트가 $0$ 인 것과 아닌 것은 $2^t$ 개씩 번갈아가면서 나타납니다.

비트가 $0$ 인 것에 $2^t$ 를 더하거나 $1$ 인 것에 $2^t$ 를 빼서 이어지므로 앞에서부터 $2^{t + 1}$ 개씩 한 연결 요소가 됩니다.

$i$ 번째 연결 요소 속 최솟값을 $m_i$ , 최댓값을 $M_i$ 라 합시다.

만약 $M_i > m_{i + 1}$ 이라면 $i + 1$ 번째 연결 요소에 $i$ 번째 연결 요소보다 작은 원소가 항상 있게 되므로 정렬이 불가능합니다. ( $A \Rightarrow B$ )

따라서 $M_i > m_{i + 1}$ 인 $i$ 의 존재는 정렬 불가능과 동치입니다.

이를 이용하면 어떤 $k$ 에 대해 정렬 불가능을 $O(n)$ 에 판단할 수 있습니다.

$f(a)$ 의 후보로 $2$ 의 거듭제곱만 살펴봐도 충분하므로 $\lfloor \log n \rfloor$ 개의 $k$ 만 살펴봐도 됩니다.

따라서 $O(n\log n)$ 에 문제를 해결할 수 있습니다.

코드 (C++)

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n, q;
    cin >> n >> q;
 
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
 
    if (is_sorted(a.begin(), a.end())) {
        cout << 0 << '\n';
        return;
    }
 
    int ans = n;
    for (int k = 1; k < n; k <<= 1) {
        int prevMax = -1;
        bool sortable = true;
 
        for (int i = 0; i < n; i += 2 * k) {
            int minValue = a[i], maxValue = a[i];
 
            for (int j = i + 1; j < min(n, i + 2 * k); j++) {
                minValue = min(minValue, a[j]);
                maxValue = max(maxValue, a[j]);
            }
 
            if (prevMax > minValue) {
                sortable = false;
                break;
            }
 
            prevMax = maxValue;
        }
 
        if (sortable) {
            ans = k;
            break;
        }
    }
 
    cout << ans << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
 
    while (t--) solve();
 
    return 0;
}

Hard Version

크기가 $2^t$ 인 블록은 $2^{t - 1}$ 인 블록 두개로 나눠서 생각할 수 있습니다.

해당 방법을 통해 전체 배열을 정렬하기 위한 최소 $k$ 를 재귀적으로 구할 수 있습니다.

쿼리가 들어오면 $i$ 가 포함된 부분배열에 대해서만 위 값을 다시 계산해주면 답을 구할 수 있습니다.

배열은 자식 배열 두 개로 나눠지므로 갱신해야 할 부분 배열의 개수는 $\log n$ 개입니다.

이는 세그먼트 트리를 이용해서 구현할 수 있습니다.

따라서 시간 복잡도 $O(n + q\log n)$ 에 해결할 수 있습니다.

코드 (C++)

#include <bits/stdc++.h>
using namespace std;
 
constexpr int INF = 2e9;
 
struct SegmentTree {
    struct Node {
        int minValue, maxValue;
        int minK;
    };
 
    vector<Node> tree;
 
    SegmentTree(int n) {
        int height = 33 - __builtin_clz(n - 1);
        tree.assign(1 << height, {INF, INF, 0});
    }
 
    void change(int node, int start, int end, int index, int value) {
        if (start == end) {
            tree[node] = {value, value, 0};
            return;
        }
 
        int mid = (start + end) / 2;
        if (index <= mid) change(node << 1, start, mid, index, value);
        else change(node << 1 | 1, mid + 1, end, index, value);
 
        if (tree[node << 1].maxValue > tree[node << 1 | 1].minValue)
            tree[node].minK = (end - start + 1) / 2;
        else tree[node].minK = max(tree[node << 1].minK, tree[node << 1 | 1].minK);
 
        tree[node].minValue = min(tree[node << 1].minValue, tree[node << 1 | 1].minValue);
        tree[node].maxValue = max(tree[node << 1].maxValue, tree[node << 1 | 1].maxValue);
    }
};
 
void solve() {
    int n, q;
    cin >> n >> q;
 
    int paddedN = (n > 1 ? 1 << (32 - __builtin_clz(n - 1)) : 2);
 
    SegmentTree seg(paddedN);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
 
        seg.change(1, 0, paddedN - 1, i, a);
    }
 
    cout << seg.tree[1].minK << '\n';
 
    while (q--) {
        int i, x;
        cin >> i >> x;
 
        seg.change(1, 0, paddedN - 1, i, x);
 
        cout << seg.tree[1].minK << '\n';
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
 
    while (t--) solve();
 
    return 0;
}

XOR Sorting

Easy Version

Hard Version

댓글

XOR Sorting

Easy Version

Hard Version

댓글