Chtholly Tree를 사용할 수 있는데 와선 세그먼트 트리를 쓰겠는가? :::align{right} ——저우 슈겐 :::

평균 \(O((n + m) \log m)\) 시간 복잡도를 가지는 Chtholly Tree 기반 해결 방안을 제시합니다.

1. 문제 개요

---

초기 수열 \([1 \dots n]\)이 주어지며, m번의 정렬 연산을 수행합니다:

• \(p = 0\): 앞 \(q\)개를 내림차순 정렬
• \(p = 1\): \(q\)부터 \(n\)까지를 오름차순 정렬

전통적인 접근법에서 매번 정렬을 직접 수행하면 단일 연산에 \(O(n \log n)\) 시간이 소요되며, 전체 시간 복잡도는 \(O(nm \log n)\)가 됩니다. 여기서 \(n,m)이 모두 \(10^5)인 경우 이는 비실용적입니다.

본 문제의 핵심 돌파구는 정렬이 교환이 아닌 순서의 재작성이며, 기존 구조를 덮어쓰기 때문입니다.

이 문제의 최종 해결법의 핵심 아이디어는 정렬이 아닌 구간 커버리지와 단조 구조 조각 유지에 있습니다.

2. 핵심 현상: 정렬은 "커버리지"와 동일

---

최종 배열은 여러 번의 교환을 통해 생성되지 않고, 여러 번의 커버리지(덮어쓰기)를 통해 구성됩니다.

그리고 최종적으로는 다음과 같은 단조 구조의 조각들로 표현됩니다:

내림차순 구간 + 내림차순 구간 + ... + 오름차순 구간 + 오름차순 구간

각 구간은 다음과 같은 특징을 가집니다:

• 단조성 (오름/내림)
• 값의 연속성 (정렬 커버리지로 인한 값의 불연속성 없음)

최소값을 기준으로 양쪽의 각 구간은:

• 값 범위가 단조적
• 값의 중복이 없음

예를 들어:

5 4 1 2 3
\       |
 \      |
 |     /
 |    /
  \__|

임의의 수평선이 두 점에서 교차하면, 이 두 점 사이의 모든 수들의 집합은 연속적입니다.

이것이 "구간 모델"의 이론적 기초입니다.

3. 그림 설명: 구간이 어떻게 구성되고 커버되는가

---

\(n = 10)의 예시를 들어 설명합니다.

10 2
0 5
1 4

초기 상태

위치: 1 2 3 4 5 6 7 8 9 10
값 : 1 2 3 4 5 6 7 8 9 10
(1 1→10 UP)

위치 \(1)에서 시작하여 숫자가 \(1)에서 \(10)까지, 방향은 UP(오름차순)입니다.

연산①: \(p = 0, q = 5) (앞 \(5)개를 내림차순으로 정렬)

\([1 \dots 5]\)를 커버합니다.

위치: 1 2 3 4 5 | 6 7 8 9 10
값 : 5 4 3 2 1 | 6 7 8 9 10
구간:(1 5→1 DOWN)+ (6 6→10 UP)

연산②: \(p = 1, q = 4) (뒤 \(7)개를 오름차순으로 정렬)

\([4 \dots 10]\)을 커버하지만, 이 구간은 "내림차순 구간 + 오름차순 구간"을 걸쳐 있습니다. \([4 \dots 5]\)를 찾습니다:

|     /    |     /
\    |     \    |
_\___|______\___|__
  \__|      |__/

커버 전 포함된 값:

위치   1 2 3 4 5 6 7 8 9 10
기존값 5 4 3 2 1 6 7 8 9 10
정렬후 5 4 3 1 2 6 7 8 9 10
(1 5→3 DOWN) + (4 1→2 UP) + (6 6→10 UP)

시각적 비유: 표면의 색상 블록을 다른 색으로 덮어쓰는 것과 같습니다

기존블록: █████□□□□□□
새블록  : ██》》》□□□□□

4. 본 문제의 사고 프레임워크

---

각 연산은:

• 해당 지점 찾기
• 커버되는 구간 삭제
• 새로운 단조 구간 추가

따라서 최종적으로 다음만 유지하면 됩니다:

• 위치 순서로 정렬된 여러 구간
• 구간에 포함된 값 범위 + 방향

set을 통해 구간을 찾고, 방향에 따라 계산하며 실제 배열 저장이 필요 없습니다.

이것이 바로 Chtholly Tree의 핵심입니다.

전체 시간 복잡도는 \(O((n + m) \log m))입니다.

5. 결과 출력

---

마지막으로 구간 순서에 따라 값을 출력합니다:

| UP인 경우   | vl → vr로 증가하며 출력 |
| DOWN인 경우 | vr → vl로 감소하며 출력 |

6. 사고 요약

---

본 문제의 본질은 정렬 문제가 아니라 구간 커버리지 문제입니다.

• 정렬은 이전 정보를 덮어쓰므로 이전 배열을 저장할 필요가 없습니다
• 각 연산은 연속적인 단조 구간을 형성합니다
• 정렬된 집합을 통해 구간 경계를 유지합니다
• 구간의 최대 크기는 연산 횟수 \(m) 이하입니다
• 최종 출력 = 구간을 순회하며 단조 방향에 따라 출력

7. 코드

---

#include<bits/stdc++.h>
#define si set<node>::iterator 
using namespace std;
struct node{
    int 시작점;
    int 최소값,최대값;
    bool isup;
    bool operator <(const node &b) const{
        return 시작점 <b.시작점;
    }
    node(int P=0,int L=0,int R=0,int U=0):시작점(P),최소값(L),최대값(R),isup(U){}
};
set<node> chtholly;
int 첫_오름차순=1;
int n,m;
int 값_가져오기(int x){
    si it=chtholly.lower_bound(node(x));
    if(it->isup)    return it->최대값-it->시작점+x;
    else    return it->최소값+it->시작점-x;
}
void 분할(int 새_시작점){
    si it=chtholly.lower_bound(node(새_시작점));
    int val=값_가져오기(새_시작점);
    if((--it)->시작점==새_시작점-1) return;
    it++;
    int p=it->시작점,l=it->최소값,r=it->최대값,f=it->isup; 
    chtholly.erase(it);
    if(f){
        chtholly.insert(node(새_시작점-1,l,val-1,1));
        chtholly.insert(node(p,val,r,1));
    }
    else{
        chtholly.insert(node(새_시작점-1,val+1,r,0));
        chtholly.insert(node(p,l,val,0));
    }
    return;
}
void 할당(int 최대값,int 새_오름차순){
    vector<node> 삭제할_리스트;
    int 최대_시작점=0,nf=-1;
    for(si F=chtholly.lower_bound(node(첫_오름차순));F!=chtholly.end();F++){
        if(F->최대값<=최대값){
            삭제할_리스트.push_back(*F);
            최대_시작점=max(최대_시작점,F->시작점);
            continue;
        }
        if(!새_오름차순)
            nf=F->시작점-(F->최대값-F->최소값);
        break;
    }
    for(si F=--chtholly.lower_bound(node(첫_오름차순));F!=chtholly.begin();F--){
        if(F->최대값 <=최대값){
            삭제할_리스트.push_back(*F);
            최대_시작점=max(최대_시작점,F->시작점);
        } else break;
    }
    for(int i=0;i<(int)삭제할_리스트.size();i++)
        chtholly.erase(삭제할_리스트[i]);
    chtholly.insert(node(최대_시작점,1,최대값,새_오름차순));
    if(nf!=-1) 첫_오름차순=nf;
    if(새_오름차순) 첫_오름차순=최대_시작점-최대값+1;
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    chtholly.insert(node(0,n+1,n+1,0));
    chtholly.insert(node(n,1,n,1));
    chtholly.insert(node(n+1,n+1,n+1,1));
    for(int i=1;i <=m;i++){
        int op,x;
        cin>>op>>x;
        if(op==0){
            분할(x+1);
            if(!chtholly.lower_bound(node(x))->isup) continue;
            else 할당(값_가져오기(x),0);
        } else{
            분할(x);
            if(chtholly.lower_bound(node(x))->isup) continue;
            else 할당(값_가져오기(x),1);
        }
    }
    for(si it=chtholly.begin();it!=chtholly.end();it++)
        if(it->isup)
            for(int i=it->최소값;i<=it->최대값;i++)
                if(i!=n+1)    cout<<i<<' ';else;
        else
            for(int i=it->최대값;i>=it->최소값;i--)
                if(i!=n+1)    cout<<i<<' ';else;
    return 0;
}