UOJ Logo negiizhao的博客

博客

Top trees用于仙人掌?O(log n)时间?带link和cut的QCACTUS?。。。

2017-12-31 23:53:07 By negiizhao

某动态的超仙人掌???

总是有出题人喜欢把序列上用线段树解决的题目出到树上,让选手强行写个树链剖分或树分治或某种动态树数据结构。

这种行为已经很无趣了。

所以我们想让大家知道,不光可以放在静态树上,动态仙人掌也是可以的。

以上都是在扯淡。

----------------

先丢个隙间吧..补完某些东西再把copy过来..

----------------

希望今天我们讲的东西能够给大家一点启发。

(希望大家不要拿这种东西出题。

(平时玩玩就算了,出到比赛里大概是会被打死的。

Open Problems:

用于仙人掌的worst-case top trees?

能否进一步将top trees推广到其他有特殊性质的图上?

科技小论文?一些奇怪的东西?QTREE系列加上link和cut?。。。

2017-12-21 01:58:29 By negiizhao

emmmmmm...前段时间学校要写个科技小论文。。。

也不知怎么的,莫名就写了个奇怪东西,反正不是论文

大概就是找来一堆论文(主要也就那几个),翻译拼凑一番(参考文献都不需要找了)。。。

把(一部分)动态树数据结构(ET-trees、ST-trees和top trees)粗略介绍了一遍。

顺便说一下,真正的top trees使用姿势可能在11页。。。对应的模板题大概是QTREE系列加上link和cut。。。

(Alstrup et al.: "Top trees generalize balanced binary search trees!")

(模板题可能还有link cut 找类似重心的东西。。。)

某些词完全就是强行翻译吧!

里面提到了重量平衡树(weight-balanced trees),这东西并不是陈立杰提出的那个。。。

并不知道他为什么要起这个名。。。不可能没有听说过weight-balanced trees。

由于ddl,很多东西就没详细说了。。。

比如self-adjusting top trees究竟是怎样的东西。

实际速度测试及对比可以看Dynamic Trees in Practice。。。

先把一些“大问题”讲清楚吧?

废话也就不多说了。。。这里是隙间。。。

最后那里赶ddl的痕迹很明显。。。很多东西都没说清楚,也懒得写了,改了title部分就丢了上来。

那个slide是论文答辩用的。。。也是赶的。。。明显少了一些东西,图没有对齐,连\pause都没加。。。

其实嘛,还考虑了一些相关的东西,但短期内不一定有时间写。

关于持久化平衡树

2017-08-27 23:04:30 By negiizhao

OI中对pointer machine常用的持久化方法称为path copying,这种方法需要复制所有发生改变的结点。复制结点会导致地址发生变化,于是也需要复制指向这个结点的结点,这样就能保证不会影响以前的版本。

曾经做过一次调查『您认为什么样的数据结构不能高效地可持久化?』,96人中有47人——即一半人选择了『使用了旋转』。事实上,path copying与是否旋转、是否完全自顶向下都是无关的,只要保证发生改变的结点都被复制了即可。

很多人用merge/split写insert/erase,但这其实是函数式的写法,常数要大一些。函数式并不等于持久化。

我在洛谷P3835进行了一些测试,目前最好的是直接使用path copying的Treap,运行时间1300~1400ms,可见是十分高效的。然而大概还是跑不过RBT

下面是参考代码。

#include <cstdio>
#include <algorithm>

using namespace std;

typedef unsigned int uint;

inline uint xorshift32()
{
    static uint seed(19260817);
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed;
}

struct IO_Tp
{
    static const int _I_Buffer_Size = 1 << 24;
    char _I_Buffer[_I_Buffer_Size];
    char* _I_pos;

    static const int _O_Buffer_Size = 1 << 24;
    char _O_Buffer[_O_Buffer_Size];
    char* _O_pos;

    IO_Tp() : _I_pos(_I_Buffer), _O_pos(_O_Buffer)
    {
        fread(_I_Buffer, 1, _I_Buffer_Size, stdin);
    }

    ~IO_Tp()
    {
        fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout);
    }

    inline bool is_digit(const char ch)
    {
        return '0' <= ch && ch <= '9';
    }

    inline IO_Tp& operator>>(int& res)
    {
        res = 0;
        while (!is_digit(*_I_pos))
            ++_I_pos;
        do
            (res *= 10) += (*_I_pos++) & 15;
        while (is_digit(*_I_pos));
        return *this;
    }

    inline int getint()
    {
        int res(0);
        bool neg(false);
        while (!is_digit(*_I_pos))
            neg = (*_I_pos++) == '-';
        do
            (res *= 10) += (*_I_pos++) & 15;
        while (is_digit(*_I_pos));
        return neg ? -res : res;
    }

    inline int getop()
    {
        static char ch;
        while (!is_digit(*_I_pos))
            ++_I_pos;
        return (*_I_pos++) & 15;
    }

    inline IO_Tp& operator<<(int n)
    {
        static char _buf[10];
        char* _pos(_buf);
        if (n < 0)
            *_O_pos++ = '-', n = -n;
        do
            *_pos++ = '0' + n % 10;
        while (n /= 10);
        while (_pos != _buf)
            *_O_pos++ = *--_pos;
        return *this;
    }

    inline IO_Tp& operator<<(char ch)
    {
        *_O_pos++ = ch;
        return *this;
    }
} IO;

const size_t _M_Size((1 << 29) - (1 << 26));
char _M[_M_Size];
char* _M_pos(_M + _M_Size);

void* operator new(size_t size)
{
    return _M_pos -= size;
}

void operator delete(void* ptr)
{
}

struct Treap
{
    int value, p, cnt, size;
    Treap* ch[2];

    Treap() : value(0), p(1 << 31), cnt(0), size(0)
    {
        ch[0] = ch[1] = this;
    }
    Treap(int v);
};

Treap* Null(new Treap);

inline Treap::Treap(const int v) : value(v), p(xorshift32()), cnt(1), size(1)
{
    ch[0] = ch[1] = Null;
}

void pushup(Treap*& o)
{
    o->size = o->ch[0]->size + o->ch[1]->size + o->cnt;
}

void copy(Treap*& o)
{
    o = new Treap(*o);
}

void rotate(Treap*& o, const bool d)
{
    Treap* c(o->ch[!d]);
    o->ch[!d] = c->ch[d];
    c->ch[d] = o;
    pushup(o), pushup(c);
    o = c;
}

void insert(Treap*& o, const int v)
{
    if (o == Null)
    {
        o = new Treap(v);
        return;
    }
    copy(o);
    if (o->value == v)
    {
        ++(o->cnt);
        ++(o->size);
        return;
    }
    bool d(o->value < v);
    insert(o->ch[d], v);
    pushup(o);
    if (o->ch[d]->p > o->p)
        rotate(o, !d);
}

Treap* merge(Treap* o[2])
{
    if (o[0] == Null)
        return o[1];
    if (o[1] == Null)
        return o[0];
    bool d(o[0]->p < o[1]->p);
    Treap* new_o(new Treap(*o[d]));
    o[d] = new_o->ch[!d];
    new_o->ch[!d] = merge(o);
    pushup(new_o);
    return new_o;
}

void erase(Treap*& o, const int v)
{
    if (o == Null)
        return;
    copy(o);
    if (o->value == v)
    {
        --(o->cnt);
        --(o->size);
        if (o->cnt == 0)
        {
            Treap* c[2] = {o->ch[0], o->ch[1]};
            o = merge(c);
        }
        return;
    }
    erase(o->ch[o->value < v], v);
    pushup(o);
}

int rank(Treap*& o, const int v)
{
    if (v == o->value || o == Null)
        return o->ch[0]->size + 1;
    return o->value < v ? o->ch[0]->size + o->cnt + rank(o->ch[1], v) : rank(o->ch[0], v);
}

int select(Treap*& o, const int k)
{
    if (o->ch[0]->size < k && k <= o->ch[0]->size + o->cnt)
        return o->value;
    return o->ch[0]->size < k ? select(o->ch[1], k - o->ch[0]->size - o->cnt) : select(o->ch[0], k);
}

int precursor(Treap*& o, const int v)
{
    if (o == Null)
        return -2147483647;
    return o->value < v ? max(o->value, precursor(o->ch[1], v)) : precursor(o->ch[0], v);
}

int successor(Treap*& o, const int v)
{
    if (o == Null)
        return 2147483647;
    return o->value > v ? min(o->value, successor(o->ch[0], v)) : successor(o->ch[1], v);
}

void debug(Treap*& o, const bool isr = true)
{
    if (o == Null)
        return;
    debug(o->ch[0], false);
    for (int i(0); i != o->cnt; ++i)
        fprintf(stderr, "%d ", o->value);
    debug(o->ch[1], false);
    if (isr)
        fputs("\n", stderr);
}

int N, now;

int main(int argc, char** argv)
{
    IO >> N;

    Treap* Root[500005] = {Null};

    while (N--)
    {
        Root[++now] = Root[IO.getint()];
        switch (IO.getop())
        {
            case 1:
                insert(Root[now], IO.getint());
                break;

            case 2:
                erase(Root[now], IO.getint());
                break;

            case 3:
                IO << rank(Root[now], IO.getint()) << '\n';
                break;

            case 4:
                IO << select(Root[now], IO.getint()) << '\n';
                break;

            case 5:
                IO << precursor(Root[now], IO.getint()) << '\n';
                break;

            case 6:
                IO << successor(Root[now], IO.getint()) << '\n';
                break;

            case 7:
                debug(Root[now]);
        }
    }

    return 0;
}
negiizhao Avatar