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$的元素之和。更新操作也大同小异。

Tree

题目描述

Give a tree with $n$ vertices, each edge has a length (positive integer less than $1001$).
Define $dist(u, v)= \text{The min distance between node} \; u \; \text{and} \; v$.
Give an integer $k$, for every pair $(u, v)$ of vertices is called valid if and only if $dist(u, v)$ not exceed $k$.
Write a program that will count how many pairs which are valid for a given tree.

题意概述

给定一棵有$n$个节点的树以及每条边的权值,问有多少个点对之间的距离不大于$k$。
数据范围:$2 \le n \le 10000$。

算法分析

考虑对于一个节点$x$以及它的子树,其中距离不大于$k$的点对要么在$x$的同一棵子树中,要么在$x$的不同子树中。后者可以递归解决,下面来解决前者。
可以统计出子树中每个节点到$x$的距离$dist_{u, x}$。显然有
$$dist_{u, v} \le k \text{且路径经过} x \Leftrightarrow dist_{u, x} + dist_{x, v} \le k \text{且} u \text{和} v \text{在不同子树中}$$
枚举$x$的子树,将前$i$棵子树中所有节点到$x$的距离用Treap维护,在处理第$(i+1)$棵子树的节点$t$时把答案加上Treap中小于等于$k-dist_{t, x}$的数的个数,即可得到答案。

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct edge {
    int v, w, nxt;
} e[20001];
struct treap {
    int tot, root;
    struct node_type {
        int val, cnt, size, rank, child[2];
    } a[10001];
    void init() { tot = root = 0; }
    void update(int t) { a[t].size = a[a[t].child[0]].size + a[a[t].child[1]].size + a[t].cnt; }
    void turn(int &t, int dire) {
        int p = a[t].child[!dire];
        a[t].child[!dire] = a[p].child[dire], a[p].child[dire] = t;
        update(t), update(p), t = p;
    }
    void insert(int &t, int val) {
        if (!t) {
            t = ++tot, a[t].rank = rand(), a[t].cnt = a[t].size = 1, a[t].val = val;
            a[t].child[0] = a[t].child[1] = 0;
            return;
        }
        ++a[t].size;
        if (val == a[t].val) ++a[t].cnt;
        else if (val < a[t].val) {
            insert(a[t].child[0], val);
            if (a[a[t].child[0]].rank < a[t].rank) turn(t, 1);
        } else {
            insert(a[t].child[1], val);
            if (a[a[t].child[1]].rank < a[t].rank) turn(t, 0);
        }
    }
    int query(int t, int val) {
        if (!t) return 0;
        if (val == a[t].val) return a[a[t].child[0]].size;
        else if (val < a[t].val) return query(a[t].child[0], val);
        else return a[a[t].child[0]].size + a[t].cnt + query(a[t].child[1], val);
    }
} tree;
long long n, k, nume, root, tot, ans, h[10001], size[10001], f[10001], val[10001];
bool vis[10001];
void add_edge(int u, int v, int w) {
    e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
    e[++nume].v = u, e[nume].w = w, e[nume].nxt = h[v], h[v] = nume;
}
void get_root(int t, int fa) {
    size[t] = 1, f[t] = 0;
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            get_root(e[i].v, t);
            size[t] += size[e[i].v];
            f[t] = max(f[t], size[e[i].v]);
        }
    }
    f[t] = max(f[t], tot - size[t]);
    if (f[t] < f[root]) root = t;
}
void get_dist(int t, int fa, int flag) {
    if (!flag) tree.insert(tree.root, val[t]);
    else ans += tree.query(tree.root, k - val[t] + 1);
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            val[e[i].v] = val[t] + e[i].w;
            get_dist(e[i].v, t, flag);
        }
    }
}
void solve(int t) {
    vis[t] = true;
    tree.init(), tree.insert(tree.root, 0);
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            val[e[i].v] = e[i].w;
            get_dist(e[i].v, t, 1);
            get_dist(e[i].v, t, 0);
        }
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            root = 0, tot = size[e[i].v];
            get_root(e[i].v, t);
            solve(root);
        }
    }
}
int main()
{
    while (scanf("%lld%lld", &n, &k)) {
        if (!n) break;
        memset(vis, 0, sizeof(vis));
        memset(h, 0, sizeof(h));
        ans = nume = 0;
        for (int i = 1; i < n; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            add_edge(u ,v, w);
        }
        tot = f[0] = n, root = 0;
        get_root(1, 0);
        solve(root);
        printf("%lld\n", ans);
    }
    return 0;
}

Book Pile

题目描述

There is a pile of $N$ books on the table. Two types of operations are performed over this pile:

  • a book is added to the top of the pile,
  • top $K$ books are rotated. If there are less than $K$ books on the table, the whole pile is rotated.

First operation is denoted as $ADD(S)$ where $S$ is the name of the book, and the second operations is denoted as $ROTATE$.
The maximum number of books is no more than $40000$. All book names are non-empty sequences of no more than $3$ capital Latin letters. The names of the books can be non-unique.

题意概述

桌上有$N$本书叠成一堆。有两种操作:①往书堆上加一本书;②将最顶上的$K$本书翻转(若不足$K$本则全部翻转)。求操作$M$次后书本的顺序。
数据范围:$0 \le N \le 40000, \; 0 \le M \le 10^5, \; 0 \le K \le 40000$。

算法分析

这题可以用Splay来做,但其实有更简单的方法。
由于只会在顶上加书,也只会翻转顶上$K$本书,所以只要维护顶上$K$本书的状态即可。建一个长度为$K$的双端队列,每次翻转相当于向队列的另一端加书,队列长度大于$K$时在加书的另一端弹出一本书(这本书不会再受到翻转影响)。