全RE？？ 求助大佬 Treap

Karis @ 2021-08-12 16:03:09

#include<iostream>
#include<cstdio>
#define R register
#define init int
#define maxn 2000010
using namespace std;
const long long INF = 2000000005;
inline init read()
{
    R init x = 0, f = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0')
    {
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

init n, m, last, root = 1, opt, ans, tot, x;
struct node{
    init l, r, data, val, size, cnt;
}t[maxn];

inline init Rand()
{
    static unsigned long long r=2333;//static不能少，r的初值可以自己定
    return (r*=233333)%=2147483647;//每次r乘上的数也可以自己定
}

int create(init val)
{
    t[++tot].val = val;
    t[tot].cnt = 1;
    t[tot].size = 1;
    t[tot].data = Rand();
}

void build()
{
    create(-INF);
    create(INF);
    t[1].r = 2;
}

void updata(init p)
{
    t[p].size = t[t[p].l].size + t[t[p].r].size + t[p].cnt;
}

void zag(init &p)
{
    init q = t[p].r;
    t[p].r = t[q].l;
    t[q].l = p;
    p = q;
    updata(p);
    updata(t[p].l);
}

void zig(init &p)
{
    init q = t[p].l;
    t[p].l = t[q].r;
    t[q].r = p;
    p = q;
    updata(p);
    updata(t[p].r);
}

void insert(init &p, init val)
{
    if(p == 0)
    {
        p = create(val);
        return;
    }
    if(t[p].val == val)
    {
        t[p].cnt++;
        return;
    }
    if(val < t[p].val)
    {
        insert(t[p].l, val);
        if(t[p].data < t[t[p].l].data)
            zig(p);
    }
    else
    {
        insert(t[p].r, val);
        if(t[p].data < t[t[p].r].data)
            zig(p);
    }
    updata(p);
}

void del(init &p, init val)
{
    if(p == 0)
        return;
    if(t[p].val == val)
    {
        if(t[p].cnt > 1)
        {
            t[p].cnt--;
            updata(p);
            return; 
        }
        if(t[p].l || t[p].r)
        {
            if(t[p].r == 0 || t[t[p].l].data > t[t[p].r].data)
            {
                zig(p);
                del(t[p].r, val);
            }
            else
            {
                zag(p);
                del(t[p].l, val);
            }
            updata(p);
        }
        else
            p = 0;
        return;
    }
    if(val < t[p].val)
        del(t[p].l, val);
    if(val > t[p].val)
        del(t[p].r, val);
    updata(p);
}

init getrank(init p, init val)
{
    if(p == 0)
        return 1;
    if(t[p].val == val)
        return t[t[p].l].size + 1;
    if(val < t[p].val)
        return getrank(t[p].l, val);
    if(val > t[p].val)
        return getrank(t[p].r, val) + t[t[p].l].size + t[p].cnt;
}

init getval(init p, init rank)
{
    if(p == 0)
        return 0;
    if(t[t[p].l].size >= rank)
        return getval(t[p].l, rank);
    if(t[t[p].l].size + t[p].cnt >= rank)
        return t[p].val;
    else
        return getval(t[p].r, rank - t[p].l - t[p].cnt);
}

init getpre(init val)
{
    init ans = 1, p = 1;
    while(p)
    {
        if(t[p].val < val)
        {
            ans = p;
            p = t[p].r;
        }
        else
            p = t[p].l;
    }
    return t[ans].val;
}

init getnext(init val)
{
    init ans = 2, p = 1;
    while(p)
    {
        if(t[p].val > val)
        {
            ans = p;
            p = t[p].l;
        }
        else
            p = t[p].r;
    }
    return t[ans].val;
}

int main()
{
    n = read();
    m = read();
    for(R int i = 1; i <= n; ++i)
    {
        R init x = read();
        insert(root, x);
    }
    while(m--)
    {
        opt = read();
        x = read();
        x ^= last;
        switch (opt)
        {
            case 1:{
                insert(root, x);
                break;
            }
            case 2:{
                del(root, x);
                break;
            }
            case 3:{
                last = getrank(root, x);
                ans ^= last;
                break;
            }
            case 4:{
                last = getval(root, x);
                ans ^= last;
                break;
            }
            case 5:{
                last = getpre(x);
                ans ^= last;
                break;
            }
            case 6:{
                last = getnext(x);
                ans ^= last;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

by Justin090102 @ 2021-08-12 16:28:31

@Petarl 还是RE，是不是我电脑问题...

by Petarl @ 2021-08-12 16:31:23

@Justin090102 啊？那我不知道

by Karis @ 2021-08-12 16:33:57

为什么会MLE

#include<iostream>
#include<cstdio>
#define R register
#define init long long
#define maxn 2000010
using namespace std;
const long long INF = 2000000005;
inline init read()
{
    R init x = 0, f = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0')
    {
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

init n, m, last, root = 1, opt, ans, tot, x;
struct node{
    init l, r, data, val, size, cnt;
}t[maxn];

inline init Rand()
{
    static unsigned long long r=2333;//static不能少，r的初值可以自己定
    return (r*=233333)%=2147483647;//每次r乘上的数也可以自己定
}

int create(init val)
{
    t[++tot].val = val;
    t[tot].cnt = 1;
    t[tot].size = 1;
    t[tot].data = Rand();
}

void build()
{
    create(-INF);
    create(INF);
    t[1].r = 2;
}

void updata(init p)
{
    t[p].size = t[t[p].l].size + t[t[p].r].size + t[p].cnt;
}

void zag(init &p)
{
    init q = t[p].r;
    t[p].r = t[q].l;
    t[q].l = p;
    p = q;
    updata(p);
    updata(t[p].l);
}

void zig(init &p)
{
    init q = t[p].l;
    t[p].l = t[q].r;
    t[q].r = p;
    p = q;
    updata(p);
    updata(t[p].r);
}

void insert(init &p, init val)
{
    if(p == 0)
    {
        p = create(val);
        return;
    }
    if(t[p].val == val)
    {
        t[p].cnt++;
        return;
    }
    if(val < t[p].val)
    {
        insert(t[p].l, val);
        if(t[p].data < t[t[p].l].data)
            zig(p);
    }
    else
    {
        insert(t[p].r, val);
        if(t[p].data < t[t[p].r].data)
            zig(p);
    }
    updata(p);
}

void del(init &p, init val)
{
    if(p == 0)
        return;
    if(t[p].val == val)
    {
        if(t[p].cnt > 1)
        {
            t[p].cnt--;
            updata(p);
            return; 
        }
        if(t[p].l || t[p].r)
        {
            if(t[p].r == 0 || t[t[p].l].data > t[t[p].r].data)
            {
                zig(p);
                del(t[p].r, val);
            }
            else
            {
                zag(p);
                del(t[p].l, val);
            }
            updata(p);
        }
        else
            p = 0;
        return;
    }
    if(val < t[p].val)
        del(t[p].l, val);
    if(val > t[p].val)
        del(t[p].r, val);
    updata(p);
}

init getrank(init p, init val)
{
    if(p == 0)
        return 1;
    if(t[p].val == val)
        return t[t[p].l].size + 1;
    if(val < t[p].val)
        return getrank(t[p].l, val);
    if(val > t[p].val)
        return getrank(t[p].r, val) + t[t[p].l].size + t[p].cnt;
}

init getval(init p, init rank)
{
    if(p == 0)
        return INF;
    if(t[t[p].l].size >= rank)
        return getval(t[p].l, rank);
    if(t[t[p].l].size + t[p].cnt >= rank)
        return t[p].val;
    else
        return getval(t[p].r, rank - t[p].l - t[p].cnt);
}

init getpre(init val)
{
    init ans = 1, p = root;
    while(p)
    {
        if(t[p].val < val)
        {
            ans = p;
            p = t[p].r;
        }
        else
            p = t[p].l;
    }
    return t[ans].val;
}

init getnext(init val)
{
    init ans = 2, p = root;
    while(p)
    {
        if(t[p].val > val)
        {
            ans = p;
            p = t[p].l;
        }
        else
            p = t[p].r;
    }
    return t[ans].val;
}

int main()
{
    n = read();
    m = read();
    for(R int i = 1; i <= n; ++i)
    {
        R init x = read();
        insert(root, x);
    }
    while(m--)
    {
        opt = read();
        x = read();
        x ^= last;
        switch (opt)
        {
            case 1:{
                insert(root, x);
                break;
            }
            case 2:{
                del(root, x);
                break;
            }
            case 3:{
                last = getrank(root, x);
                ans ^= last;
                break;
            }
            case 4:{
                last = getval(root, x);
                ans ^= last;
                break;
            }
            case 5:{
                last = getpre(x);
                ans ^= last;
                break;
            }
            case 6:{
                last = getnext(x);
                ans ^= last;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}