用无旋treap做需要哨兵节点吗? 就是处理边界的那种?

P3391 【模板】文艺平衡树

Zolrk @ 2018-09-12 07:23:50

看网上有博客说需要设置,但是我没设置也过了(bzoj上也过了) 既然两个oj上的数据都能通过,我实在不明白不设置边界节点到底会出什么问题

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int MAXN = 100000 + 10;

struct trnode{
    int val,lz,rnd,ls,rs,siz;
}tr[MAXN];

int n,m,tot,root;

void update(int now) {
    tr[now].siz = tr[tr[now].ls].siz + tr[tr[now].rs].siz + 1;
}

void down(int now) {
    tr[now].lz ^= 1;
    swap(tr[now].ls, tr[now].rs);
    tr[tr[now].ls].lz ^= 1;
    tr[tr[now].rs].lz ^= 1;
}

int new_node(int val) {
    tr[++tot].val = val;
    tr[tot].siz = 1;
    tr[tot].rnd = rand();
    tr[tot].lz = 0; 
    return tot;
}

int build(int l, int r) {
    if(l > r) return 0;
    int mid = l+r>>1;
    int pos = new_node(mid);
    tr[pos].ls = build(l, mid-1);
    tr[pos].rs = build(mid+1, r);
    update(pos);
    return pos;
}

int merge(int x, int y) { //将xy合并
    if(!x || !y) return x + y; 
    if(tr[x].lz) down(x);
    if(tr[y].lz) down(y);
    if(tr[x].rnd < tr[y].rnd) {
        tr[x].rs = merge(tr[x].rs, y);
        update(x);
        return x;
    } else {
        tr[y].ls = merge(x, tr[y].ls);
        update(y);
        return y;
    }
}

void split(int now, int k, int &x, int &y) { 
    if(!now) x = y = 0;
    else {
        if(tr[now].lz) down(now);
        if(k <= tr[tr[now].ls].siz) 
            y = now, split(tr[now].ls, k, x, tr[now].ls); 
        else 
            x = now, split(tr[now].rs, k-tr[tr[now].ls].siz-1, tr[now].rs, y);
        update(now);
    }

}

void reverse(int l, int r) {
    int a,b,c,d;
    split(root, r, a, b);
    split(a, l-1, c, d);
    tr[d].lz ^= 1;
    root = merge(merge(c, d), b);
}

void dfs(int now) {
    if(tr[now].lz) down(now);
    if(tr[now].ls) dfs(tr[now].ls);
    printf("%d ", tr[now].val);
    if(tr[now].rs) dfs(tr[now].rs);
}

int main() {
    scanf("%d %d", &n, &m);
    root = build(1, n);
    for(int i=1; i<=m; i++) { 
        int l,r;
        scanf("%d %d", &l, &r);
        reverse(l, r);
    }
    dfs(root);
    return 0;
}

by i207M @ 2018-09-12 07:26:26

你又不是指针。。。


by Zolrk @ 2018-09-12 07:28:56

@i207M 不懂欸。。。网上那些博客也是数组版的,为什么指针会出锅?是不是因为指到了空的位置会怎么怎么样?


by Mr_Spade @ 2018-09-12 09:04:49

不需要


|