LibreOJ 104 - 일반 밸 런 스 트 리 (밸 런 스 트 리)

이것 은 템 플 릿 문제 다.
하나의 시퀀스 를 유지 하기 위해 서 는 데이터 구조 (제목 제목 참조) 를 써 야 합 니 다. 그 중에서 다음 과 같은 조작 을 제공 해 야 합 니 다.
한 구간 을 뒤 집 는데, 예 를 들 어 기 존 서열 이 543, 21 이 고, 뒤 집기 구간 이 [2, 4] 이면 결 과 는 523, 4 1 이다.
사고방식 이라는 문 제 는 회전 이 없 는 treap 의 구간 조작 을 구현 하 였 다.
관건 값 에 따라 정렬 할 수 없 으 며, 현재 노드 의 위치 에 따라 정렬 해 야 합 니 다.업데이트 과정 에서 현재 노드 를 유지 하기 전에 몇 개의 노드 (cnct) 가 있 습 니까?
이렇게 하면 treap 는 구간 을 분열 시 킬 수 있다.분 단 된 후에 합병 하면 treap 의 구 조 를 바 꾸 지만 treap 의 중간 순 서 를 바 꾸 지 않 습 니 다.따라서 질서 있 는 서열 이 있 으 면 이 를 treap 에 삽입 합 니 다. 분 단 된 treap 의 중간 순 서 는 바로 이 질서 있 는 서열 의 특정한 하위 서열 입 니 다.그래서 이 treap 를 이 하위 서열 로 보고 여러 가지 조작 을 할 수 있 습 니 다.
뒤 집기 구간 은 구간 [l, r] 의 treap 를 분열 시 킨 다음 각 결점 의 좌우 자 결점 을 교환 하 는 것 이다.
왜 이렇게 할 수 있 지?중간 순서 가 옮 겨 다 니 는 순 서 는:
왼쪽 결점, 이 결점, 오른쪽 결점.이렇게 하면 순서대로 출력 할 수 있다.
만약 당신 이 swap 서브 트 리 의 모든 결점 의 좌우 결점 은
오른쪽 결점, 이 결점, 왼쪽 결점 의 순 서 를 옮 겨 다 니 면 결 과 는 순서 가 뒤 집 히 는 것 (역순) 으로 뒤 집 히 는 것 과 같다.게 으 름 표시 (선분 트 리 와 유사) 를 사용 하여 불필요 한 반전 을 줄 일 수 있 습 니 다.
또한 모든 결점 의 좌우 자 결점 을 교환 하면 쌓 인 성질 을 바 꾸 지 않 고 뒤 집 힌 후에 도 합 법 적 인 treap 이다.
Copy
`#include
include
include
include
include
include
include
include
include
include
include
include
include
include
define endl 'n'
define IOS std::ios::sync_with_stdio(0);
define FILE freopen("..//data_generator//in.txt","r",stdin),freopen("res.txt","w",stdout)
define FI freopen("..//data_generator//in.txt","r",stdin)
define FO freopen("res.txt","w",stdout)
define pb cpush_back
define mp make_pair
define seteps(N) fixed << setprecision(N)
typedef long long ll;using namespace std;/-----------------------------------------------------------------/
define INF 0x3f3f3f3f
const int N = 1e6 + 10;const int M = 1e9 + 7;const double eps = 1e-8;
int pos[N];int lc[N], rc[N];int val[N];int cnt[N];int lazy[N];int si;
typedef pair PII;
void pushdown(int rt) {

if(lazy[rt]) {
    swap(lc[rt], rc[rt]);
    lazy[lc[rt]]++;
    lazy[rc[rt]]++;
    lazy[lc[rt]] %= 2;
    lazy[rc[rt]] %= 2;
    lazy[rt] = 0;
}

}
PII split(int rt, int key) {

if(!key || !rt) {
    return mp(0, rt);
}
pushdown(rt);
if(key < cnt[lc[rt]] + 1) {
    PII o = split(lc[rt], key);
    lc[rt] = o.second;
    cnt[rt] = cnt[lc[rt]] + cnt[rc[rt]] + 1;
    return mp(o.first, rt);
} else {
    PII o = split(rc[rt], key - cnt[lc[rt]] - 1);
    rc[rt] = o.first;
    cnt[rt] = cnt[lc[rt]] + cnt[rc[rt]] + 1;
    return mp(rt, o.second);
}

}
int merge(int lrt, int rrt) {

if(!lrt) return rrt;
if(!rrt) return lrt;
pushdown(lrt);
pushdown(rrt);
if(pos[lrt] > pos[rrt]) {
    rc[lrt] = merge(rc[lrt], rrt);
    cnt[lrt] = cnt[lc[lrt]] + cnt[rc[lrt]] + 1;
    return lrt;
} else {
    lc[rrt] = merge(lrt, lc[rrt]);
    cnt[rrt] = cnt[lc[rrt]] + cnt[rc[rrt]] + 1;
    return rrt;
}

}
int insert(int v, int rt) {

++si;
val[si] = v;
pos[si] = rand();
cnt[si] = 1;
return merge(rt, si);

}
void print(int rt) {

if(!rt) return ;
pushdown(rt);
print(lc[rt]);
cout << val[rt] << " "; 
print(rc[rt]);

}
int reverse(int l, int r, int rt) {

int tar;
PII o1 = split(rt, r);
tar = o1.first;
PII o2 = o1;
if(l > 1) {
    o2 = split(tar, l - 1);
    tar = o2.second;
}
lazy[tar] = 1;
if(l > 1) return merge(merge(o2.first, o2.second), o1.second);
return merge(o1.first, o1.second);

}
int main() {

IOS;
//FO;
int n, m;
cin >> n >> m;
int rt = 0;
for(int i = 1; i <= n; i++) {
    rt = insert(i, rt);
}
while(m--) {
    int l, r;
    cin >> l >> r;
    rt = reverse(l, r, rt);
}
print(rt);

}`