题解 P3871 【[TJOI2010]中位数】

GaoZiyou · 2018-10-30 22:50:51 · 题解

居然没有链表的题解

本蒟蒻就来一发

【思路】

离线处理，先把所有要加进去的数都加入链表中，然后对链表排序，这样操作中加入一个数的操作就可以转化为倒序的删除一个数，不难发现，删除一个数后，中位数只会更新为它的前驱或后继，用一个指针扫描即可求出中位数。

【实现】

• 链表结点的定义

  struct Node {
  int val, pre, suc;
  Node(int val = 0, int pre = 0, int suc = 0): val(val), pre(pre), suc(suc) {}
  } l[N << 1];

  val表示权值，pre、suc分别表示前驱、后继

• 存储操作

  struct Oper {
  int op, p, ans;
  } c[N];

  op=1表示添加，p表示连续倒序操作时要删除的链表结点的指针
  op=0表示查询，ans记录答案

• 如何对链表排序

  struct cmp {
  bool operator()(int x, int y) { return l[x].val < l[y].val; }
  };
  for (int i = 1; i <= tot; ++i) t[i] = i;
  sort(t + 1, t + tot + 1, cmp());

  建立辅助数组t，保证每个添加操作的指针不会丢失

• 删除一个结点后指针如何移动

  int now = t[(tot + 1) / 2];
  int a = (tot + 1) / 2 - 1, b = tot - a - 1;
  for (int i = m; i >= 1; --i)
  if (c[i].op == 1) {
    int p = c[i].p;
    if (rank[p] <= rank[now])
      --a;
    else
      --b;
    if (p == now) now = l[now].pre;
    Link(l[p].pre, l[p].suc);
    if (a + 1 < b)
      now = l[now].suc, ++a, --b;
    if (a > b)
      now = l[now].pre, --a, ++b;
  } else {
    c[i].ans = l[now].val;
  }
  }

  now表示当前中位数结点的指针
  a表示比当前中位数小的数的个数
  b表示比当前中位数大的数的个数
  分类讨论一下就行了
  注意特判删除的结点为中位数的情况

【代码】

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int n, m, t[N << 1], tot, rank[N << 1];
char str[4];

struct Node {
  int val, pre, suc;
  Node(int val = 0, int pre = 0, int suc = 0): val(val), pre(pre), suc(suc) {}
} l[N << 1];

struct Oper {
  int op, p, ans;
} c[N];

inline void Link(int x, int y) {
  l[x].suc = y, l[y].pre = x;
}

struct cmp {
  bool operator()(int x, int y) { return l[x].val < l[y].val; }
};

int main() {
  scanf("%d", &n);
  for (int i = 1, x; i <= n; ++i) {
    scanf("%d", &x);
    l[++tot] = Node(x);
  }
  scanf("%d", &m);
  for (int i = 1, x; i <= m; ++i) {
    scanf("%s", str);
    if (str[0] == 'a') {
      c[i].op = 1;
      scanf("%d", &x);
      l[++tot] = Node(x);
      c[i].p = tot;
    } else {
      c[i].op = 0;
    }
  }
  for (int i = 1; i <= tot; ++i) t[i] = i;
  sort(t + 1, t + tot + 1, cmp());
  for (int i = 1; i <= tot; ++i)
    rank[t[i]] = i;
  for (int i = 1; i < tot; ++i)
    Link(t[i], t[i + 1]);
  int now = t[(tot + 1) / 2];
  int a = (tot + 1) / 2 - 1, b = tot - a - 1;
  for (int i = m; i >= 1; --i)
    if (c[i].op == 1) {
      int p = c[i].p;
      if (rank[p] <= rank[now])
        --a;
      else
        --b;
      if (p == now) now = l[now].pre;
      Link(l[p].pre, l[p].suc);
      if (a + 1 < b)
        now = l[now].suc, ++a, --b;
      if (a > b)
        now = l[now].pre, --a, ++b;
    } else {
      c[i].ans = l[now].val;
    }
  for (int i = 1; i <= m; ++i)
    if (c[i].op == 0) printf("%d\n", c[i].ans);
  return 0;
}