fhq求助

P3391 【模板】文艺平衡树

Semorius @ 2021-11-19 11:46:48

#include <bits/stdc++.h>
using namespace std;
const int SIZE = 100005;
int n, m, tot, root;
int ch[SIZE][2], size[SIZE], val[SIZE], rnd[SIZE];
bool tag[SIZE];
int X, Y, Z;

inline int rd(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1)+(x<<3)+(ch^48);
        ch = getchar();
    }
    return x*f;
}

void pushup(int p){
    size[p] = size[ch[p][0]] + size[ch[p][1]] + 1;
}

void pushdown(int p){
    if(tag[p]){
        swap(ch[p][0], ch[p][1]);
        if(ch[p][0]) tag[ch[p][0]] ^= 1;
        if(ch[p][1]) tag[ch[p][1]] ^= 1;
        tag[p] = 0;
    }
}

int New(int x){
    ch[++tot][0] = ch[tot][1] = 0;
    size[tot] = 1; val[tot] = x;
    rnd[tot] = rand();
    return tot;
}

void split(int now, int k, int &x, int &y){
    if(!now) x = y = 0;
    else{
        pushdown(now);
        if(val[now] <= k) x = now, split(ch[now][1], k, ch[now][1], y);
        else y = now, split(ch[now][0], k, x, ch[now][0]);
        pushup(now);
    }   
}

int merge(int A, int B){
    if(!A || !B) return A + B;
    if(rnd[A] < rnd[B]){
        pushdown(A);
        ch[A][1] = merge(ch[A][1], B);
        pushup(A);
        return A;
    }
    else{
        pushdown(B);
        ch[B][0] = merge(A, ch[B][0]);
        pushup(B);
        return B;
    }
}

void change(int l, int r){
    split(root, r, X, Y);
    split(X, l-1, Z, X);
    tag[X] ^= 1;
    root = merge(merge(Z, X), Y);   
}

void Print(int p){
    if(!p) return;
    if(tag[p]) pushdown(p);
    Print(ch[p][0]);
    printf("%d ", val[p]);
    Print(ch[p][1]);
}

int main(){
    srand(time(0));
    n = rd(), m = rd();
    for(int i = 1; i <= n; i++){
        root = merge(root, New(i));
    }
    for(int i = 1; i <= m; i++){
        int l = rd(), r = rd();
        change(l, r);
    }
    Print(root);
    return 0;
}
/*
5 10
1 3
2 4
1 5
2 3
3 5
1 2
2 3
3 4
1 3
1 5
*/

by jerry3128 @ 2021-11-19 11:50:43

是有pushdown的时候才交换的一种实现方式,没有问题。

不常见,原因是容易炸,容易出锅。


by Semorius @ 2021-11-19 11:52:55

所以要怎么改呢


by wwlw @ 2021-11-19 11:56:34

@shiyihangxs 你尝试 change 的时候就把儿子换了,pushdown 的时候直接 change 儿子


by w23c3c3 @ 2021-11-19 12:06:34

change 的时候应该按 rank split 吧。


by Semorius @ 2021-11-19 12:07:12

@wwlw 好像不是pushdown的问题,换成排名分裂就过了


by wwlw @ 2021-11-19 12:08:27

按权值 split 有什么问题吗 /jk


by Semorius @ 2021-11-19 12:08:33

所以什么时候用权值,什么时候用排名


by Semorius @ 2021-11-19 12:09:07

感觉也没啥问题


by wwlw @ 2021-11-19 12:13:16

草,肯定不能按权值 split,权值都变了


|