RBTree 10s多, FhqTreap 16.5s都可以过，但是Splay TLE了一些测试点1与4，有啥可以优化的地方吗？

#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define LOCAL 0
#define CONFIG_USE_RBTREE 0
#define CONFIG_USE_SPLAY 0
#define CONFIG_USE_TREAP 1
#define MAXN 1100000

struct SplayNode {
  int32_t key;
  int size;
  int cnt;
  SplayNode *left;
  SplayNode *right;
  SplayNode *parent;
};

SplayNode splay[MAXN];
int id;

SplayNode *MakeSplayNode(int32_t key)
{
  SplayNode *node = &splay[id];
  ++id;
  node->key = key;
  node->size = 1;
  node->cnt = 1;
  node->left = nullptr;
  node->right = nullptr;
  node->parent = nullptr;
  return node;
}

void UpdateField(SplayNode *p)
{
  p->size = p->cnt;
  if (p->left != nullptr) {
    p->size += p->left->size;
  }
  if (p->right != nullptr) {
    p->size += p->right->size;
  }
}

void LeftRotate(SplayNode *&root, SplayNode *p)
{
  SplayNode *q = p->right;
  p->right = q->left;
  if (q->left != nullptr) {
    q->left->parent = p;
  }
  q->parent = p->parent;
  if (p->parent != nullptr) {
    if (p->parent->left == p) {
      p->parent->left = q;
    } else {
      p->parent->right = q;
    }
  } else {
    root = q;
  }
  q->left = p;
  p->parent = q;
  q->size = p->size;
  UpdateField(p);
}

void RightRotate(SplayNode *&root, SplayNode *p)
{
  SplayNode *q = p->left;
  p->left = q->right;
  if (q->right != nullptr) {
    q->right->parent = p;
  }
  q->parent = p->parent;
  if (p->parent != nullptr) {
    if (p->parent->left == p) {
      p->parent->left = q;
    } else {
      p->parent->right = q;
    }
  } else {
    root = q;
  }
  q->right = p;
  p->parent = q;
  q->size = p->size;
  UpdateField(p);
}

void Splay(SplayNode *&root, SplayNode *p)
{
  while (p != root) {
    if (p->parent->parent == nullptr) {
      if (p == p->parent->left) {
        RightRotate(root, p->parent);
      } else {
        LeftRotate(root, p->parent);
      }
    } else if (p->parent->left == p && p->parent->parent->left == p->parent) {
      RightRotate(root, p->parent->parent);
      RightRotate(root, p->parent);
    } else if (p->parent->right == p && p->parent->parent->right == p->parent) {
      LeftRotate(root, p->parent->parent);
      LeftRotate(root, p->parent);
    } else if (p->parent->left == p && p->parent->parent->right == p->parent) {
      RightRotate(root, p->parent);
      LeftRotate(root, p->parent);
    } else {
      LeftRotate(root, p->parent);
      RightRotate(root, p->parent);
    }
  }
}

SplayNode *SplayPredecessor(SplayNode *&root, SplayNode *p)
{
  SplayNode *q;
  if (p->left != nullptr) {
    p = p->left;
    while (p->right != nullptr) {
      p = p->right;
    }
    Splay(root, p);
    return p;
  } else {
    q = p->parent;
    while (q!=nullptr && p==q->left) {
      p = q;
      q = q->parent;
    }
    if (q != nullptr) {
      Splay(root, q);
    }
    return q;
  }
}

SplayNode *SplaySuccessor(SplayNode *&root, SplayNode *p)
{
  SplayNode *q;
  if (p->right != nullptr) {
    p = p->right;
    while (p->left != nullptr) {
      p = p->left;
    }
    Splay(root, p);
    return p;
  } else {
    q = p->parent;
    while (q!=nullptr && p==q->right) {
      p = q;
      q = q->parent;
    }
    if (q != nullptr) {
      Splay(root, q);
    }
    return q;
  }
}

SplayNode *SplayInsert(SplayNode *root, SplayNode *node)
{
  SplayNode *p, *q, *f;
  p = root;
  f = nullptr;
  while (p != nullptr) {
    f = p;
    if (node->key < p->key) {
      p = p->left;
    } else {
      p = p->right;
    }
  }
  node->parent = f;
  if (f != nullptr) {
    if (node->key < f->key) {
      f->left = node;
    } else {
      f->right = node;
    }
  } else {
    root = node;
  }
  q = f;
  while (q!= nullptr) {
    ++q->size;
    q = q->parent;
  }
  Splay(root, node);
  return root;
}

SplayNode *SplayJoin(SplayNode *root1, SplayNode *root2)
{
  int choose;
  SplayNode *p;
  if (root1 == nullptr) {
    return root2;
  } else if (root2 == nullptr) {
    return root1;
  } else {
    choose = (root1->size > root2->size) || (root1->size==root2->size && (root1->size&0x01));
    if (choose) {
      p = root1;
      while (p->right != nullptr) {
        p = p->right;
      }
      Splay(root1, p);
      root1->right = root2;
      root2->parent = root1;
      root1->size += root2->size;
      return root1;
    } else {
      p = root2;
      while (p->left != nullptr) {
        p = p->left;
      }
      Splay(root2, p);
      root2->left = root1;
      root1->parent = root2;
      root2->size += root1->size;
      return root2;
    }
  }
}

//assume node is already in the root tree
SplayNode *SplayDelete(SplayNode *root, SplayNode *node)
{
  Splay(root, node);
  if (root->left != nullptr) {
    root->left->parent = nullptr;
  }
  if (root->right != nullptr) {
    root->right->parent = nullptr;
  }
  root = SplayJoin(root->left, root->right);
  return root;
}

pair<SplayNode *, SplayNode *> SplaySearch(SplayNode *&root, int32_t key)
{
  SplayNode *p = root, *f = nullptr;
  while (p != nullptr) {
    if (key < p->key) {
      f = p;
      p = p->left;
    } else if (key > p->key) {
      f = p;
      p = p->right;
    } else {
      break;
    }
  }
  if (p!=nullptr) {
    Splay(root, p);
  }
  return make_pair(p, f);
}

int SplayRank(SplayNode *&root, int32_t key)
{
  int rank = 0;
  SplayNode *p = root;
  while (p!= nullptr) {
    if (key < p->key) {
      p = p->left;
    } else if (key > p->key) {
      rank += p->cnt;
      if (p->left!=nullptr) {
        rank += p->left->size;
      }
      p = p->right;
    } else {
      if (p->left!=nullptr) {
        rank += p->left->size;
      }
      Splay(root, p);
      break;
    }
  }
  return rank;
}

SplayNode *SplaySelect(SplayNode *&root, int rank)
{
  SplayNode *p = root;
  while (p!=nullptr) {
    if (p->left != nullptr && rank < p->left->size) {
      p = p->left;
    } else {
      if (p->left != nullptr) {
        rank -= p->left->size;
      }
      if (rank < p->cnt) {
        break;
      } else {
        rank -= p->cnt;
        p = p->right;
      }
    }
  }
  if (p!=nullptr) {
    Splay(root, p);
  }
  return p;
}

SplayNode *InsertDuplicated(SplayNode *root, SplayNode *node)
{
  Splay(root, node);
  ++node->size;
  ++node->cnt;
  return root;
}

SplayNode *DeleteDuplicated(SplayNode *root, SplayNode *node)
{
  Splay(root, node);
  --node->size;
  --node->cnt;
  return root;
}

int ReadInteger(void)
{
  int x=0, sign=1;
  int ch;
  ch = getchar();
  while (ch<'0' || ch>'9') {
    if (ch=='-') {
      sign = -1;
    }
    ch = getchar();
  }
  while (ch>='0' && ch<='9') {
    x = x*10 + ch-'0';
    ch = getchar();
  }
  return x*sign;
}

int main(void)
{
#if LOCAL
  freopen("test.in", "r", stdin);
  freopen("test.out", "w", stdout);
#endif
  int n, m, rank=0;
  int op;
  int32_t x, last=0, ans=0;
  n = ReadInteger();
  m = ReadInteger();
  SplayNode *root = nullptr, *node;
  pair<SplayNode *, SplayNode *> node_pair;
  id = 0;
  for (int i=0; i<n; ++i) {
    x = ReadInteger();
    node_pair = SplaySearch(root, x);
    node = node_pair.first;
    if (node==nullptr) {
      node = MakeSplayNode(x);
      root = SplayInsert(root, node);
    } else {
      root = InsertDuplicated(root, node);
    }
  }
  for (int i=0; i<m; ++i) {
    op = ReadInteger();
    x = ReadInteger();
    x ^= last;
    switch (op) {
    case 1:
      node_pair = SplaySearch(root, x);
      node = node_pair.first;
      if (node==nullptr) {
        node = MakeSplayNode(x);
        root = SplayInsert(root, node);
      } else {
        root = InsertDuplicated(root, node);
      }
      break;
    case 2:
      node_pair = SplaySearch(root, x);
      node = node_pair.first;
      if (node != nullptr) {
        if (node->cnt == 1) {
          root = SplayDelete(root, node);
        } else {
          root = DeleteDuplicated(root, node);
        }
      }
      break;
    case 3:
      rank = SplayRank(root, x);
      last = rank+1;
      ans ^= last;
      break;
    case 4:
      rank = x-1;
      node = SplaySelect(root, rank);
      if (node != nullptr) {
        last = node->key;
        ans ^= last;
      }
      break;
    case 5:
      node_pair = SplaySearch(root, x);
      node = node_pair.first;
      if (node != nullptr) {
        node = SplayPredecessor(root, node);
      } else {
        node = node_pair.second;
        if (x < node->key) {
          node = SplayPredecessor(root, node);
        }
      }
      if (node != nullptr) {
        last = node->key;
        ans ^= last;
      }
      break;
    case 6:
      node_pair = SplaySearch(root, x);
      node = node_pair.first;
      if (node != nullptr) {
        node = SplaySuccessor(root, node);
      } else {
        node = node_pair.second;
        if (x > node->key) {
          node = SplaySuccessor(root, node);
        }
      }
      if (node != nullptr) {
        last = node->key;
        ans ^= last;
      }
      break;
    }
  }
  printf("%d\n", ans);
  return 0;
}