HNOI2004 宠物收养所 splay 入门

平衡二叉树的入门题，最近在研究 splay，就做了下，感觉题目不错，就写了。

这题就是简单的元素插入删除操作，注意一下绝对值相同的时候取较小的即可，还有就是每次收养所里要么都是人，要么都是宠物。

这里用到一个 $type$ 变量记录树种元素是人还是宠物，如果是 - 1 表示空

这样每次取得一个数，如果和树种类型一致，就加入树种，否则就在树中寻找绝对值离它最近点一个即可。

代码写的比较长，有些是这道题不需要的函数，主要是为了封装，全部写了出来，可以当模板用。只是多元素的处理没有弄好，如果有重复元素，$rank$ 和 $selete$ 函数以及结构体的封装就要换一下了。

我的代码：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int mod = 1000000;
const int MAX = 150000;
const int oo = 0x3f3f3f3f;
typedef int keyType;

struct Node {
  keyType key;
  int size;
  Node* son[2];
  Node* fa;
} node[MAX], nil, *null;
Node* root;
int st[MAX], top, K;

Node* New() {
  if (top) {
    return &node[st[--top]];
  } else {
    return &node[K++];
  }
}

void Delete(Node* ptr) { st[top++] = ptr - node; }

void update(Node* x) {
  x->size = 1;
  for (int i = 0; i < 2; i++) {
    if (x->son[i] != null) {
      x->size += x->son[i]->size;
    }
  }
}

void rotate(Node* x, const int& w) {
  Node* y;
  y = x->fa;
  y->son[1 - w] = x->son[w];
  if (x->son[w] != null) {
    x->son[w]->fa = y;
  }
  x->fa = y->fa;
  if (y->fa != null) {
    if (y == y->fa->son[0]) {
      y->fa->son[0] = x;
    } else {
      y->fa->son[1] = x;
    }
  }
  x->son[w] = y;
  y->fa = x;
  update(y);
  update(x);
}

void splay(Node* x, Node* y) {
  while (x->fa != y) {
    if (x->fa->fa == y) {
      if (x == x->fa->son[0]) {
        rotate(x, 1);
      } else {
        rotate(x, 0);
      }
    } else {
      if (x->fa == x->fa->fa->son[0]) {
        if (x == x->fa->son[0]) {
          rotate(x->fa, 1);
          rotate(x, 1);
        } else {
          rotate(x, 0);
          rotate(x, 1);
        }
      } else {
        if (x == x->fa->son[1]) {
          rotate(x->fa, 0);
          rotate(x, 0);
        } else {
          rotate(x, 1);
          rotate(x, 0);
        }
      }
    }
  }
  if (y == null) {
    root = x;
  }
}

void addNode(Node* x, Node* father, keyType val) {
  x->key = val;
  x->fa = father;
  x->son[0] = x->son[1] = null;
  x->size = 1;
}
void insert(keyType x) {
  Node *y, *z;
  if (root == null) {
    y = New();
    root = y;
    addNode(y, null, x);
    return;
  }
  y = root;
  do {
    y->size++;
    if (x < y->key) {
      if (y->son[0] != null) {
        y = y->son[0];
      } else {
        z = New();
        addNode(z, y, x);
        y->son[0] = z;
        y = z;
        break;
      }
    } else {
      if (y->son[1] != null) {
        y = y->son[1];
      } else {
        z = New();
        addNode(z, y, x);
        y->son[1] = z;
        y = z;
        break;
      }
    }
  } while (true);
  splay(y, null);
}

Node* find(keyType x) {
  Node* y;
  y = root;
  do {
    if (y->key == x) {
      break;
    }
    if (x < y->key) {
      if (y->son[0] == null) {
        break;
      } else {
        y = y->son[0];
      }
    } else {
      if (y->son[1] == null) {
        break;
      } else {
        y = y->son[1];
      }
    }
  } while (true);
  splay(y, null);
  return y;
}

bool exist(keyType x) {
  Node* y;
  y = root;
  while (y != null && y->key != x) {
    if (x < y->key) {
      y = y->son[0];
    } else {
      y = y->son[1];
    }
  }
  if (y != null) splay(y, null);
  return y != null;
}

void init() {
  nil.size = 0;
  null = &nil;
  K = 0;
  top = 0;
  root = null;
}

void Delete(keyType x) {
  Node *y, *z;
  y = find(x);
  splay(y, null);
  if (y->son[0] == null) {
    if (y->son[1] == null) {
      init();
    } else {
      root = y->son[1];
      y->son[1]->fa = null;
    }
  } else {
    z = y->son[0];
    while (z->son[1] != null) z = z->son[1];
    splay(z, y);
    z->son[1] = y->son[1];
    if (y->son[1] != null) {
      y->son[1]->fa = z;
    };
    z->fa = null;
    root = z;
    update(z);
  }
}

keyType selete(int x) {
  Node* y;
  y = root;
  while (1) {
    if (x <= y->son[0]->size) {
      y = y->son[0];
    } else {
      if (x == y->son[0]->size + 1) {
        break;
      } else {
        x = x - y->son[0]->size - 1;
        y = y->son[1];
      }
    }
  }
  splay(y, null);
  return y->key;
}

void deleteNums(keyType x) {
  Node* y;
  if (root == null) {
    return;
  }
  y = find(x);
  splay(y, null);
  y->son[1] = null;
  if (y->key >= x) {
    if (y->son[0] == null) {
      init();
    } else {
      root = y->son[0];
      y->son[0]->fa = null;
    }
  }
}

int rank(keyType x) {
  Node* y;
  if (root == null) {
    return 0;
  }
  y = find(x);
  splay(y, null);
  return y->son[0]->size + (int)(y->key <= x);
}

keyType maxSmall(keyType x) {
  Node* y;
  if (root == null) {
    return -oo;
  }
  y = find(x);
  splay(y, null);
  if (y->key > x) {
    y = y->son[0];
    if (y == null) {
      return -oo;
    }
    while (y->son[1] != null) {
      y = y->son[1];
    }
  }
  return y->key;
}

keyType minBig(keyType x) {
  Node* y;
  if (root == null) {
    return oo;
  }
  y = find(x);
  splay(y, null);
  if (y->key < x) {
    y = y->son[1];
    if (y == null) {
      return oo;
    }
    while (y->son[0] != null) {
      y = y->son[0];
    }
  }
  return y->key;
}

int cnt, ret;

void run(int x) {
  int t1, t2;
  t1 = minBig(x);
  t2 = maxSmall(x);
  if (t1 == oo) {
    ret = (ret + abs(x - t2)) % mod;
    Delete(t2);
    cnt--;
  } else if (t2 == -oo) {
    ret = (ret + abs(x - t1)) % mod;
    Delete(t1);
    cnt--;
  } else if (abs(x - t1) < abs(x - t2)) {
    ret = (ret + abs(x - t1)) % mod;
    Delete(t1);
    cnt--;
  } else if (abs(x - t1) == abs(x - t2)) {
    if (t1 < t2) {
      ret = (ret + abs(x - t1)) % mod;
      Delete(t1);
      cnt--;
    } else {
      ret = (ret + abs(x - t2)) % mod;
      Delete(t2);
      cnt--;
    }
  } else {
    ret = (ret + abs(x - t2)) % mod;
    Delete(t2);
    cnt--;
  }
}

int main() {
  int n;
  int x, op;
  int type;
  while (~scanf("%d", &n)) {
    init();
    type = -1;
    cnt = 0;
    ret = 0;
    for (int i = 0; i < n; i++) {
      scanf("%d%d", &op, &x);
      if (type == -1 || type == op) {
        type = op;
        insert(x);
        cnt++;
      } else {
        run(x);
        if (!cnt) {
          type = -1;
        }
      }
    }
    printf("%d\n", ret);
  }
  return 0;
}