代码通过了 P6136 【模板】普通平衡树（数据加强版） 但修改后没过 P3369 【模板】普通平衡树

仅改了main函数 P6136的代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

static const int maxn = 1100100;
static const int inf = 0x7FFFFFFF;

inline int input()
{
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    
    long long x = c - '0'; c = getchar();
    while (c >= '0' && c <= '9')
    {
        x = x * 10 - '0' + c;
        c = getchar();
    }
    return (int)x;
}

struct Node
{
    int l, r;
    int val, dat;
    int cnt, size;
};
Node T[maxn];
int tot = 0, root;

int New(int val)
{
    T[++tot].val = val;
    T[tot].dat = rand();
    T[tot].cnt = T[tot].size = 1;
    return tot;
}

void Update(int p)
{ T[p].size = T[T[p].l].size + T[T[p].r].size + T[p].cnt; }

void Build()
{
    New(-inf); New(inf);
    root = 1; T[1].r = 2;
    Update(root);
}

int GetRankbyVal(int p, int val)
{
    if (!p) return 0;
    if (val == T[p].val) return T[T[p].l].size + 1;
    if (val  < T[p].val) return GetRankbyVal(T[p].l, val);
    int rRank = GetRankbyVal(T[p].r, val);
    return rRank + T[T[p].l].size + T[p].cnt + (rRank == 0);
}

int GetValbyRank(int p, int rank)
{
    if (!p) return inf;
    if (rank <= T[T[p].l].size) return GetValbyRank(T[p].l, rank);
    if (rank <= T[T[p].l].size + T[p].cnt) return T[p].val;
    return GetValbyRank(T[p].r, rank - T[T[p].l].size - T[p].cnt);
}

void zig(int &p)
{
    int q = T[p].l;
    T[p].l = T[q].r; T[q].r = p, p = q;
    Update(T[p].r); Update(p);
}

void zag(int &p)
{
    int q = T[p].r;
    T[p].r = T[q].l; T[q].l = p, p = q;
    Update(T[p].l); Update(p);
}

void Insert(int &p, int val)
{
    if (!p) { p = New(val); return; }
    if (val == T[p].val) { T[p].cnt++; Update(p); return; } 
    
    if (val  < T[p].val)
    {
        Insert(T[p].l, val);
        if (T[p].dat < T[T[p].l].dat) zig(p);
    }
    
    if (val  > T[p].val)
    {
        Insert(T[p].r, val);
        if (T[p].dat < T[T[p].r].dat) zag(p);
    }
    Update(p);
}

void Remove(int &p, int val)
{
    if (!p) return;
    if (val == T[p].val)
    {
        if (T[p].cnt > 1)
        {
            T[p].cnt--; Update(p);
            return;
        }
        if (T[p].l || T[p].r)
        {
            if (!T[p].r || T[T[p].l].dat > T[T[p].r].dat)
                zig(p), Remove(T[p].r, val);
            else
                zag(p), Remove(T[p].l, val);
            Update(p);
        }
        else p = 0;
        return;
    }
    (val < T[p].val)? Remove(T[p].l, val) : Remove(T[p].r, val);
    Update(p);
}

int GetPrev(int val)
{
    int ans = 1;
    int p = root;
    while (p)
    {
        if (val == T[p].val)
        {
            if (T[p].l)
            {
                p = T[p].l;
                while (T[p].r) p = T[p].r;
                ans = p;
            }
            break;
        }   
        if (T[p].val < val && T[p].val > T[ans].val) ans = p;
        p = (val < T[p].val)? T[p].l : T[p].r;
    }
    return T[ans].val;
}

int GetNext(int val)
{
    int ans = 2;
    int p = root;
    while (p)
    {
        if (val == T[p].val)
        {
            if (T[p].r)
            {
                p = T[p].r;
                while (T[p].l) p = T[p].l;
                ans = p;
            }
            break;
        }
        if (T[p].val > val && T[p].val < T[ans].val) ans = p;
        p = (val < T[p].val)? T[p].l : T[p].r; 
    }
    return T[ans].val;
}

void print(int p)
{
    if (!p) return;
    printf("(%d %d) ", T[p].val, T[p].cnt);
    print(T[p].l); print(T[p].r);
}

int N, M;

int main()
{
    memset(T, 0, sizeof(T));
    srand(time(NULL)); Build();
    N = input(); M = input();
    for (int i = 1; i <= N; i++)
    {
        int v = input();
        Insert(root, v);
    }
    
    int ans = 0, last = 0; 
    for (int i = 1; i <= M; i++)
    {
        int opt, v;
        opt = input(); v = input() ^ last;
        switch (opt)
        {
            case 1: Insert(root, v); break;
            case 2: Remove(root, v); break;
            case 3: ans ^= (last = GetRankbyVal(root, v) - 1); break;
            case 4: ans ^= (last = GetValbyRank(root, v + 1)); break; 
            case 5: ans ^= (last = GetPrev(v)); break; 
            case 6: ans ^= (last = GetNext(v)); break; 
        }
    }
    printf("%d\n", ans);
    return 0;
}

P3396的main函数:

int main()
{
    memset(T, 0, sizeof(T));
    srand(time(NULL)); Build();
    N = input();
    
    for (int i = 1; i <= N; i++)
    {
        int opt, v;
        opt = input(); v = input();
        switch (opt)
        {
            case 1: Insert(root, v); break;
            case 2: Remove(root, v); break;
            case 3: printf("%d\n", GetRankbyVal(root, v) - 1); break;
            case 4: printf("%d\n", GetValbyRank(root, v + 1)); break; 
            case 5: printf("%d\n", GetPrev(v)); break; 
            case 6: printf("%d\n", GetNext(v)); break; 
        }
    }
    return 0;
}

P6136的提交记录 P3369的提交记录