有没有兄弟看看哪有问题,五个点全WA了,我下了第一个测试点,输出的数据没问题。

P3391 【模板】文艺平衡树

Keyzee @ 2022-07-22 17:03:30

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
const int MAXN = 100005;
const int MOD = 2147483647;

struct Node
{
    int left;      //左子树
    int right;     //右子树
    int size;      //大小
    int val;       //值
    int key;       //平衡种子
    int lazy;

}tree[MAXN];

int root, tot;

int add(int val) {
    tot++;
    tree[tot].size = 1;
    tree[tot].val = val;
    tree[tot].key = rand() % MOD;
    tree[tot].left = 0;
    tree[tot].right = 0;

    return tot;
}

void update_root(int now) {
    int left, right;

    left = tree[now].left;
    right = tree[now].right;

    tree[now].size = tree[left].size + tree[right].size + 1;
}

void pushdown(int x) {
    if (tree[x].lazy) {
        tree[tree[x].left].lazy ^= 1;
        tree[tree[x].right].lazy ^= 1;
        swap(tree[x].left, tree[x].right);
        tree[x].lazy ^= 1;
    }
}

//拆分(now原treap,a左子树,b右子树,val值)
void split_val (int now, int& a, int& b, int val) {
    if (now == 0) {
        a = 0;
        b = 0;
        return;
    }

    if (tree[now].val <= val) {//now左子树中的所有值都小于now,
        a = now;
        split_val(tree[now].right, tree[a].right, b, val);
    }
    else {
        b = now;
        split_val(tree[now].left, a, tree[b].left, val);
    }

    update_root(now);
}

void split_k(int now, int& a, int& b, int k) {
    if (now == 0) {
        a = 0;
        b = 0;
        return;
    }
    pushdown(now);
    if (tree[tree[now].left].size < k) {
        a = now;
        split_k(tree[now].right, tree[a].right, b, k - tree[tree[now].left].size - 1);
    }
    else {
        b = now;
        split_k(tree[now].left, a, tree[b].left, k);
    }

    update_root(now);
}

void merge_new(int& now, int a, int b) {
    if (a == 0 || b == 0) {
        now = a + b;
        return;
    }
    pushdown(a), pushdown(b);
    //按照key值合并(堆性质)
    if (tree[a].key < tree[b].key) {
        /**
         * a树key值小于b树,那么b树属于a树的后代,因为b树恒大于a树,那么b树一定属于a树的右后代,
         * a的左子树不变,直接赋给now,递归合并a的右子树和b
         */
        now = a;
        merge_new(tree[now].right, tree[a].right, b);
    }
    else {
        now = b;
        merge_new(tree[now].left, a, tree[b].left);
    }

    update_root(now);
}

void find_new(int now, int rank) {//找第k大
    while (tree[tree[now].left].size + 1 != rank) {
        if (tree[tree[now].left].size >= rank) {
            now = tree[now].left;
        }
        else {
            rank -= tree[tree[now].left].size + 1;
            now = tree[now].right;
        }
    }
    cout << tree[now].val << "\n";
}

void insert_new(int val) {
    int x, y, z;

    x = 0;
    y = 0;
    z = add(val);
    split_val(root, x, y, val);
    merge_new (x, x, z);
    merge_new(root, x, y);
}

void del_new(int val) {
    int x, y, z;

    x = y = z = 0;
    split_val(root, x, y, val);
    split_val(x, x, z, val - 1);
    merge_new(z, tree[z].left, tree[z].right);
    merge_new(x, x, z);
    merge_new(root, x, y);
}

void get_rank(int val) {
    int x, y;

    x = y = 0;
    split_val(root, x, y, val - 1);
    cout << tree[x].size + 1 << "\n";
    merge_new(root, x, y);
}

void get_val(int rank) {
    find_new(root, rank);
}

void get_pre(int val) {
    int x, y;

    x = y = 0;
    split_val(root, x, y, val - 1);
    find_new(x, tree[x].size);
    merge_new(root, x, y);
}

void get_next(int val) {
    int x, y;

    x = y = 0;
    split_val(root, x, y, val);
    find_new(y, 1);
    merge_new(root, x, y);
}

void rever(int l, int r) {
    int a, b, c, d;
    split_k(root, a, b, r);
    split_k(a, c, d, l - 1);
    tree[d].lazy ^= 1;
    int rt;
    merge_new(rt, c, d);
    merge_new(root, rt, b);
}
int n, m;
int cnt = 1;
int flag = 0;
void print(int x) {
    if (!x)return;
    pushdown(x);
    print(tree[x].left);
    if (cnt == n && flag) return;
    if (cnt != n) {
        cout << tree[x].val << " ";
        cnt++;
    }
    else {
        cout << tree[x].val;
        flag = 1;
    }
    print(tree[x].right);
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    //int n, m;
    cin >> n >> m;

    memset(tree, 0, sizeof(tree));

    add(MOD);
    root = 1;
    tree[root].size = 0;

    for (int i = 1; i <= n; i++) {
        insert_new(i);
    }
    for (; m; --m) {
        int x, y;
        cin >> x >> y;
        rever(x, y);
    }
    print(1);
    //cout << "\n";

    return 0;
}

|