萌新求助

P3391 【模板】文艺平衡树

Treaker @ 2019-09-22 16:27:46

交上去全部RE , Debug时splay函数出锅了,但感觉没问题啊。。

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100005;
inline int read()
{
    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 << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    return x * f;
}
int n , m , cnt;
struct Splay
{
    struct node
    {
        node *ch[2] , *fa;
        int val , size , tag;
        node(node *fa = NULL,int val = 0,int size = 0) : fa(fa) , val(val) , size(size) {ch[0] = ch[1] = NULL;tag = 0;}
        inline bool isr() {return this == fa -> ch[1];}
        inline int rk() {return 1 + (ch[0] ? ch[0] -> size : 0);}
        inline void up() {size = (ch[0] ? ch[0] -> size : 0) + (ch[1] ? ch[1] -> size : 0) + 1;}
        inline void down()
        {
            swap(ch[0],ch[1]);
            if(ch[0])   ch[0] -> tag ^= 1;
            if(ch[1])   ch[1] -> tag ^= 1;
            tag = 0;
        }
    }*root;
    inline void rot(node *x)
    {
        bool k = x -> isr();
        node *y = x -> fa; node *z = y -> fa; node *w = x -> ch[!k];
        if(y == root)   root = x;
        else z -> ch[y -> isr()] = x;
        x -> ch[!k] = y; y -> ch[k] = w;
        y -> fa = x;x -> fa = z;
        if(w) w -> fa = y;
        y -> up(); x -> up();
    }
    inline void splay(node *x,node *goal)
    {
        while(x -> fa != goal)
        {
            if(x -> fa -> fa != goal)   rot(x -> isr() ^ x -> fa -> isr() ? x : x -> fa);
            rot(x);
        }
        if(goal == NULL)    root = x;
    }
    void build(int l,int r,node *&p,node *fa)
    {
        if(l > r)   return;
        int mid = (l + r) >> 1;
        p = new node(fa,mid,1);
        build(l,mid-1,p -> ch[0],p);
        build(mid+1,r,p -> ch[1],p);
        p -> up();
//      printf("%d %d %d\n",l,r,p -> size);
    }
    inline node *kth(int k)
    {
        node *p = root;
        while(p && p -> rk() != k)
        {
            if(p -> tag) p -> down();
//          printf("dasdas %d %d %d %d %d ",p -> val,p -> rk(),k,p -> ch[0] -> val,p -> ch[0] -> rk());
            if(p -> rk() > k)   p = p -> ch[0];
            else k -= p -> rk() , p = p -> ch[1];
//          printf("???\n");
        }
        return p;
    }
    inline void reverse(int l,int r)
    {
        node *x = kth(l); node *y = kth(r+2);
        splay(x,NULL);
        splay(y,root);
        y -> ch[0] -> tag ^= 1;
    }
    void dfs(node *p)
    {
        if(p == NULL)   return;
        if(p -> tag) p -> down();
        if(p -> ch[0])  dfs(p -> ch[0]);
        if(p -> val >= 1 && p -> val <= n) printf("%d ",p -> val);
        if(p -> ch[1])  dfs(p -> ch[1]);
    }
    inline void LOL()
    {
        n = read(); m = read();
        build(0,n+1,root,NULL);
        for(int i = 1 , l , r;i <= m;i ++)
        {
            ++cnt ;
            l = read(); r = read();
            reverse(l,r);
        }
        dfs(root);
    }
}DNF;
int main()
{
    DNF.LOL();
    return 0;
}
/*
100 3
47 91
11 15
45 57
*/

@zh_dou @__wfx @wlj_dy


by Treaker @ 2019-09-22 16:44:26

@Froggy ???


by Treaker @ 2019-09-22 16:46:28

@Froggy 不用交换吧 -.- 之前普通平衡树就这样写的


by Froggy @ 2019-09-22 16:49:26

@Treaker 看错了QAQ,splay函数好象没问题


by Treaker @ 2019-09-22 16:50:41

@Froggy 但是就是运行splay的时候RE了,难受-.-


by Froggy @ 2019-09-22 16:51:53

@Treaker 我是mx,不会指针,QAQ


by Treaker @ 2019-09-22 16:53:03

@Froggy qnmdmx


by Treaker @ 2019-09-22 16:54:16

@Froggy 表示还是很谢谢


上一页 |