Sum of Medians

题目描述

In one well-known algorithm of finding the $k$-th order statistics we should divide all elements into groups of five consecutive elements and find the median of each five. A median is called the middle element of a sorted array (it’s the third largest element for a group of five). To increase the algorithm’s performance speed on a modern video card, you should be able to find a sum of medians in each five of the array.

A sum of medians of a sorted $k$-element set $S={a_1, a_2, \ldots, a_k}$, where $a_1 \lt a_2 \lt a_3 \lt \cdots \lt a_k$, will be understood by as $\sum_{i \bmod 5=3} a_i$.

The $\bmod$ operator stands for taking the remainder, that is $x \bmod y$ stands for the remainder of dividing $x$ by $y$.

To organize exercise testing quickly calculating the sum of medians for a changing set was needed.

题意概述

有一个初始为空的集合。有三种操作：① 向集合中加入一个元素，保证操作前这个元素不存在；② 从集合中删除一个元素，保证操作前这个元素存在；③ 询问集合中元素排序后下标模$5$余$3$的元素之和。共有$n$次操作。

数据范围：$1 \le n \le 10^5$。

算法分析 1

直接用平衡树来维护。对于每个节点储存它子树的大小以及它子树排序后下标模$5$余$0$、余$1$、…、余$4$的元素之和。显然，一个节点的左子树可以直接更新当前节点，而右子树则需根据左子树的大小进行处理后再更新当前节点。

代码 1

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
long long n, x;
string o;
struct treap {
  int tot, root;
  struct node_type {
    int child[2], rank;
    long long val, size, mod[5];
  } node[100001];
  void update(int t) {
    node[t].size = node[node[t].child[0]].size + node[node[t].child[1]].size + 1;
    for (int i = 0; i < 5; ++i)
      node[t].mod[i] = node[node[t].child[0]].mod[i] + node[node[t].child[1]].mod[(i + 99999 - node[node[t].child[0]].size) % 5];
    node[t].mod[(node[node[t].child[0]].size + 1) % 5] += node[t].val;
  }
  void rotate(int &t, int dire) {
    int p = node[t].child[!dire];
    node[t].child[!dire] = node[p].child[dire], node[p].child[dire] = t;
    update(t), update(p), t = p;
  }
  void insert(int &t, long long val) {
    if (!t) {
      t = ++tot, node[t].rank = ((rand() & ((1 << 16) - 1)) << 10) ^ rand(), node[t].val = node[t].mod[1] = val, node[t].size = 1;
      return;
    }
    ++node[t].size;
    if (val < node[t].val) {
      insert(node[t].child[0], val);
      if (node[node[t].child[0]].rank > node[t].rank) rotate(t, 1);
    } else {
      insert(node[t].child[1], val);
      if (node[node[t].child[1]].rank > node[t].rank) rotate(t, 0);
    }
    update(t);
  }
  void remove(int &t, long long val) {
    if (!node[t].child[0] && !node[t].child[1]) { t = 0; return; }
    if (val == node[t].val) {
      if (node[node[t].child[0]].rank > node[node[t].child[1]].rank) rotate(t, 1);
      else rotate(t, 0);
    }
    if (val < node[t].val) remove(node[t].child[0], val);
    else remove(node[t].child[1], val);
    update(t);
  }
  long long query() { return node[root].mod[3]; }
} tree;
int main()
{
  srand(time(NULL));
  cin >> n;
  while (n--) {
    cin >> o;
    if (o[0] == 'a') { cin >> x; tree.insert(tree.root, x); }
    else if (o[0] == 'd') { cin >> x; tree.remove(tree.root, x); }
    else cout << tree.query() << endl;
  }
  return 0;
}

算法分析 2

将操作离线，并将所有操作数离散化，用线段树来维护离散后的区间。和平衡树类似，对于每个节点储存区间内的元素个数以及区间内的元素排序后下标模$5$余$0$、余$1$、…、余$4$的元素之和。更新操作也大同小异。