关于此题ODT做法
查看原帖
关于此题ODT做法
891245
R_aier楼主2023/10/29 09:56

这个ODT是哪写错了吗?

mt19937 mt;
struct ODT
{
    struct node
    {
        int len = 0, siz = 0, pri = 0, ls = 0, rs = 0, sum = 0;
        bool val;
    } t[maxn << 2];
    int rt, cnt;
#define ls(u) t[u].ls
#define rs(u) t[u].rs
#define len(u) t[u].len
#define sum(u) t[u].sum
#define siz(u) t[u].siz
#define pri(u) t[u].pri
#define val(u) t[u].val
    int new_node(bool val, int len = 1)
    {
        if(len==0) return 0;
        t[++cnt] = node{len, len, (int)mt(), 0, 0, val * len, val};
        return cnt;
    }
    void push_up(int u)
    {
        siz(u) = siz(ls(u)) + siz(rs(u)) + len(u);
        sum(u) = sum(ls(u)) + sum(rs(u)) + len(u) * val(u);
    }
    int merge(int l, int r)
    {
        if (!l || !r)
            return l | r;
        if (pri(l) < pri(r))
        {
            rs(l) = merge(rs(l), r);
            push_up(l);
            return l;
        }
        else
        {
            ls(r) = merge(l, ls(r));
            push_up(r);
            return r;
        }
    }
    int split(int u, int siz)
    {
        int v = new_node(val(u), len(u) - siz);
        len(u) = siz;
        rs(v) = rs(u);
        rs(u) = 0;
        return v;
    }
    bool ll;
    void split(int u, int x, int &l, int &r)
    {
        if (!u)
        {
            l = r = 0;
            return;
        }
        if (siz(ls(u)) > x)
        {
            r = u;
            split(ls(u), x, l, ls(u));
        }
        else if (siz(ls(u)) + len(u) < x)
        {
            l = u;
            split(rs(u), x - siz(ls(u)) - len(u), rs(u), r);
        }
        else
        {
            if (siz(ls(u)) == x)
            {
                l = ls(u);
                r = u;
                ls(u) = 0;
            }
            else if (siz(ls(u)) + len(u) == x)
            {
                l = u;
                r = rs(u);
                rs(u) = 0;
            }
            else
            {
                x -= siz(ls(u));
                r = split(u, x);
                l = u;
                push_up(l);
                push_up(r);
            }
        }
        push_up(u);
    }
    void change(int l, int r, bool b)
    {
        int L = 0, R = 0, p = 0;
        split(rt, l - 1, L, p);
        split(p, r - l + 1, p, R);
        int _0 = new_node(0, siz(p) - sum(p)), _1 = new_node(1, sum(p));
        p = merge(b ? _1 : _0, b ? _0 : _1);
        rt = merge(L, merge(p, R));
    }
    bool query(int u, int k)
    {
        if (siz(ls(u)) > k)
            return query(ls(u), k);
        if (siz(ls(u)) + len(u) < k)
            return query(rs(u), k - siz(ls(u)) - len(u));
        return val(u);
    }
    bool query(int k)
    {
        return query(rt, k);
    }
    int build(int l, int r)
    {
        if (l > r)
            return 0;
        int mid = (l + r) >> 1;
        int u = new_node(b[mid]);
        ls(u) = build(l, mid - 1);
        rs(u) = build(mid + 1, r);
        push_up(u);
        return u;
    }
    void init()
    {
        cnt = 0;
        rt = build(1, n);
    }
} t;
2023/10/29 09:56
加载中...