斯坦纳树

经典题：HDU4085

简述

在一棵树上对关键点集进行运算的一种灵活的数据结构。

区间除和开方要解决的就是以下两种操作：

1. \(\forall i \in [l, r], \lfloor \frac{a_i}{d} \rfloor \to a_i\)
2. \(\forall i \in [l, r], \lfloor \sqrt{a_i} \rfloor \to a_i\)

正常的标记操作是很难实现这些操作的，然而我们可以把这些操作进行一些转换，因为这些操作在一定的值域范围内是可以批量处理的。换句话说，如果区间内极差小，那么除法或开方的效果在区间内等效，所以可以转化成减法来进行实现。

拿除法举例：在区间\((l, r)\)中，如果\( \max(S) – \lfloor \frac{\max(S)}{d} \rfloor = \min(S) – \lfloor \frac{\min(S)}{d} \rfloor \)，那么我们就可以把这个差值作为减数，用正常的加减方式进行标记。

Continue reading →

性质

节点内子树的值都比本身要小（堆的性质），且整个子树在序列上是一段连续的子串。

建树方式和例题

HDU-1506 单调栈的裸题。

// HDU-1506.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 1e5 + 200;

struct node
{
    int ch[2], idx, fa, val;
    void clear() { ch[0] = ch[1] = idx = fa = val = 0; }
} nodes[MAX_N];

int n, stk[MAX_N << 1], top;
ll ans;

int build()
{
    for (int i = 1; i <= n; i++)
    {
        int k = i - 1;
        while (nodes[k].val > nodes[i].val)
            k = nodes[k].fa;
        nodes[i].ch[0] = nodes[k].ch[1];
        nodes[k].ch[1] = i;
        nodes[i].fa = k, nodes[nodes[i].ch[0]].fa = i;
    }
    return nodes[0].ch[1];
}

int dfs(int u)
{
    if (u == 0)
        return 0;
    int siz = 1;
    for (int bit = 0; bit < 2; bit++)
        siz += dfs(nodes[u].ch[bit]);
    ans = max(ans, 1LL * siz * nodes[u].val);
    return siz;
}

int main()
{
    while (scanf("%d", &n) && n != 0)
    {
        ans = 0;
        nodes[0].ch[0] = nodes[0].ch[1] = nodes[0].idx = nodes[0].fa = nodes[0].val = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &nodes[i].val), nodes[i].idx = i, nodes[i].fa = 0;
            memset(nodes[i].ch, 0, sizeof(nodes[i].ch));
        }
        dfs(build());
        printf("%lld\n", ans);
    }
    return 0;
}

D – Numbers of Permutations

思考量很小的一道题。

先用间接法来算。初始答案为\(n!\)，然后考虑容斥掉那些符合排序规则的方案。发现，我们可以分开来考虑，按照容斥的顺序：先考虑只算第一维、第二维的，在加回来两维都考虑的。

第一维和第二维的做法非常显然：排序之后用多重集的排列就行了，考虑每一个相同的区间里面内部乘起来。如果有\(k\)个连续的数段，那么部分的答案就是\(\prod_{i = 1}^l len_k!\)。

Continue reading →