Luogu 3642 [APIO 2016] 烟火表演

传送门

引例（上一道题）

凸函数

  回忆我们上一道题是怎么做的。我们维护的东西的实质是一个（下）凸函数。由于我们的操作相当于是加上一个凸函数，而凸函数与凸函数的和仍然为凸函数。我们只保存斜率发生变化的点，利用题目给函数带来的特殊性质，只用这些点的横坐标就计算出了答案。

一开始的思路

  不难发现，如果最后的时间过长，那么一定会浪费；如果最后时间过短，那么也会有不必要的缩短，感性地理解，好像二分答案可做。不过我们没有办法进行可行性检验。

正解

  根据前面的思路，我们可以发现：若设 fi(x) f i ( x ) $f_i(x)$ 表示以 i i $i$ 为根的子树需要 x$x$$x$ 秒去引爆时的最小代价，那么 fi(x) f i ( x ) $f_i(x)$ 是一个（下）凸函数。

  我们考虑在子树 u u $u$ 的根结点上加上它父亲连向它的一条边权为 w$w$$w$ 的边对 fu(x) f u ( x ) $f_u(x)$ 的影响。我们先设 [L,R] [ L , R ] $[L, R]$ 表示 fi(x) f i ( x ) $f_i(x)$ 斜率为 0 0 $0$ 的那一段的左右端点。

$$f_u(x) = \begin{cases} f_{u'}(x) + w & x \le L & \text{让新的边权为 } 0 \\ f_{u'}(L) + (w - (x - L)) & L < x \le L + w & \text{让新的边权为 } x - L \\ f_{u'}(L) & L + w < x \le R + w & \text{让新的边权为 } w \\ f_{u'}(L) + ((x - R) - w) & R + w < x & \text{让新的边权为 } x - R \end{cases}$$

  其中 fu(x) f u ( x ) $f_u(x)$ 表示新函数， fu′(x) f u ′ ( x ) $f_{u'}(x)$ 表示原函数。显然，最后的答案为 f1(x1) f 1 ( x 1 ) $f_1(x_1)$，其中 xi x i $x_i$ 表示使得 fi(x) f i ( x ) $f_i(x)$ 取得最小值的 x x $x$。

---

  我们先来理解下为什么状态转移方程是这样的。首先需要注意的是，我们设的 x$x$$x$ 与上一道题的 x x $x$ 并不一样，所以转移的方法肯定也不一样。

  可以知道，x=x′+w′(w′≥0)$x=x^{\prime }+w^{\prime }(w^{\prime }\ge 0)$$x = x' + w' \pod{w' \ge 0}$，其中 x′ x ′ $x'$ 表示原来引爆的总时间， w′ w ′ $w'$ 表示最后决定把这条边的边权从 w w $w$ 变成 w′$w^{\prime }$$w'$。当 x≥L x ≥ L $x \ge L$ 时，我们要令 w′ w ′ $w'$ 越小越好，因为当 x′ x ′ $x'$ 越小（即 w′ w ′ $w'$ 越大）时，为了让原来引爆的总时间变成 x′ x ′ $x'$ 的代价就越高，且斜率 ≤−1 ≤ − 1 $\le -1$，而修改 w w $w$ 的单位代价仅为 1$1$$1$，所以这并不划算，因此我们令 w′=0 w ′ = 0 $w' = 0$。对于第二部分，我们保证 x′=L x ′ = L $x' = L$ 就好，这样我们可以少减少 w w $w$。由于最终 w′=x−L$w^{\prime }=x-L$$w' = x - L$（这样才有 x′=L x ′ = L $x' = L$），因此花费的代价是 w−(x−L) w − ( x − L ) $w - (x - L)$。对于第三部分，我们不用改变 w w $w$ 都保证了 L≤x≤R$L\le x\le R$$L \le x \le R$，因此不需要操作。对于第四部分，由于越往后斜率越大，且至少为 1 1 $1$，而我们修改 w$w$$w$ 的单位代价为 1 1 $1$，同时我们可以无限制地加长 w$w$$w$，因此我们选择让 x′=R x ′ = R $x' = R$，所以花费的代价就是 (x−R)−w ( x − R ) − w $(x - R) - w$。

---

  我们来仔细分析一下这个过程究竟干了什么。首先很明显，对于 x≤L x ≤ L $x \le L$ 的部分，我们把它向上平移了 w w $w$ 个单位。对于第二部分，我们从第一部分的结尾开始画了一条斜率为 −1$-1$$-1$ ，（横坐标）长度为 w w $w$ 的直线，到第三个部分，我们接着画了一条斜率为 0$0$$0$，长度为 R−L R − L $R - L$ 的直线，再到第四个部分，我们接着画了一条斜率为 1 1 $1$ 的直线，一直延伸到正无穷……

  有没有感觉跟上一道题的图形有点像？可以发现，各关键点间形成的直线的斜率是递增的。但是这个递增对我们来说暂时还没有什么用，毕竟到这里我都还完全做不来。我们应该仔细看看这个函数有没有其它性质，因为我们能够维护的只有拐点的横坐标，我们必须通过这些横坐标算出我们想要的信息（就像上一题一样，我们把答案拆开来算，因此就不用管最后的函数值了）。

---

  我们发现：利用上面的函数进行转移时，函数的斜率一定会是 ⋯,−3,−2,−1,0,1$\cdots ,-3,-2,-1,0,1$$\cdots, -3, -2, -1, 0, 1$，如果某个斜率不存在，那也一定在某个位置有两个重合的点，我们把它视作一个长度为 0 0 $0$ 的区间，认为它仍然存在。

证明
  当一开始这个函数为空时，进行转移相当于是叶结点接上了父结点，这时，我们得到了斜率为 −1$-1$$-1$ 和 1 1 $1$ 的两条直线，我们视它中间存在一条长度为 0$0$$0$ 且斜率为 0 0 $0$ 的直线。
  当我们对一个符合条件的函数进行转移时，我们相当于是在斜率为 −1$-1$$-1$ 和斜率为 0 0 $0$ 的直线的拐点处增加了一条斜率为 −1$-1$$-1$ 的直线，这并不影响函数的这个性质。故这个性质成立。

  为什么要规定函数有这么一个性质（你有没有觉得我们的强行规定使得这个东西很没说服力？）？因为 f(0) f ( 0 ) $f(0)$ 是相当好求的：就是所有导火索的原长度之和。如果我们知道了所有拐点的位置，我们只需要减去一定的值，就能算出 f(L) f ( L ) $f(L)$ 了。

  像上一道题一样，我们得到了只需要拐点坐标就求得所需函数值的方法，岂不美哉？

---

  考虑程序实现。对于叶结点，我们只需要在 w w $w$ 处插入两个点就好了，它左边代表一条斜率为 −1$-1$$-1$ 的直线，中间代表一条斜率为 0 0 $0$ 的直线（长度为 0$0$$0$），右边代表一条斜率为 1 1 $1$ 的直线。对于一棵树，我们将所有儿子对应子树的函数加起来就好了。不难发现，通过保存拐点，函数仍然满足前面我们规定的性质。那么，怎么维护函数取得最小值时的横坐标呢？

  这需要结合我们的转移对函数的影响进行考虑。我们的转移只会增加一条斜率为 1$1$$1$ 的直线，并且我们用最右边的拐点对它进行表示。当多个函数加起来时，有多少个函数，斜率的最大值就为多少。我们在维护时保留 R R $R$ 端点，那么我们只需要在合并后删除坐标最大的 k$k$$k$ 个拐点就好了， k k $k$ 代表儿子个数。（但是为了方便，为了让叶结点和非叶结点进行统一，我们要保存 R$R$$R$，也就是说只删除 k−1 k − 1 $k - 1$ 个拐点就可以了）

  那么怎么考虑非叶结点的转移呢？由于插入了一条斜率为 −1 − 1 $-1$，长度为 w w $w$ 的直线，因此斜率为 0$0$$0$ 的那一段相当于是向右平移了 w w $w$ 个单位。我们删除原来的拐点，重新插入在新的位置即可（因为 0$0$$0$ 左边的直线斜率为 −1 − 1 $-1$，所以不用再插入新的拐点，相当于是斜率为 −1 − 1 $-1$ 的直线变长了）。

  最后，我们只保留 L L $L$ 及其左边的拐点，然后依次减去它们的横坐标，正好就是我们要的函数值。

（灵魂之图）

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
    putchar('\n');
}

template <typename T, typename C = std::less<T> >
class priority_queue
{
    struct Node
    {
        T v;
        int dis;
        Node* ch[2];
        Node() : v(), dis(-1), ch() {}
        Node(const T& v) : v(v), dis(0), ch() {}
    };
    Node* root;
    int s;

private:
    void operator=(const priority_queue&) {} // 禁止拷贝

public:
    priority_queue() : root(), s() {}
    ~priority_queue() { clear(); }

private:
    void clear(Node* &r)
    {
        if (!r) return;
        clear(r->ch[0]);
        clear(r->ch[1]);
        delete r;
        r = NULL;
    }
public:
    void clear() { clear(root); }

public:
    int size() { return s; }
    bool empty() { return !s; }

    // significant below
private:
    static Node* merge(Node* a, Node* b)
    {
        if (!b) return a;
        if (!a) return b;
        if (C()(b->v, a->v)) std::swap(a, b);
        a->ch[1] = merge(a->ch[1], b);
        if (!a->ch[0] || (a->ch[1] && a->ch[1]->dis > a->ch[0]->dis)) // note
            std::swap(a->ch[0], a->ch[1]);
        if (a->ch[1])
            a->dis = a->ch[1]->dis + 1;
        else
            a->dis = 0;
        return a;
    }
public:
    void merge(priority_queue& b)
    {
        root = merge(root, b.root);
        s += b.s;
        b.root = NULL;
        b.s = NULL;
    }

public:
    void push(const T& x)
    {
        root = merge(root, new Node(x));
        s++;
    }
    const T& top() const
    {
        return root->v;
    }
    void pop()
    {
        Node* del = root;
        root = merge(root->ch[0], root->ch[1]);
        delete del;
        s--;
    }
};

// if (x <= L) f[x] += w; // 让新的边权为 0
// if (L < x && x <= L + w) f[x] = f[L] + (w - (x - L)); // 让新的边权为 x - L
// if (L + w < x && x <= R + w) f[x] = f[L]; // 让新的边权为 w
// if (x > R + w) f[x] = f[L] + ((x - R) - w); // 让新的边权为 x - R

const int maxn = int(6e5) + 5;
int n, m, E;
int degree[maxn];
int parent[maxn];
int weight[maxn];
priority_queue<long long, std::greater<long long> > pq[maxn];
LL sum;

void run()
{
    n = readIn();
    m = readIn();
    for (int i = 2; i <= n + m; i++)
    {
        degree[parent[i] = readIn()]++;
        sum += weight[i] = readIn();
    }
    for (int i = n + m; i > 1; i--)
    {
        long long l = 0, r = 0;
        if (i <= n)
        {
            for (int j = 1; j < degree[i]; j++)
                pq[i].pop(); // 最后留下了 L 和 R
            r = pq[i].top();
            pq[i].pop();
            l = pq[i].top();
            pq[i].pop();
        }
        pq[i].push(l + weight[i]);
        pq[i].push(r + weight[i]);
        pq[parent[i]].merge(pq[i]); // 合并到父结点
    }
    for (int i = 1; i <= degree[1]; i++)
        pq[1].pop(); // 最后只剩下了 L
    while (pq[1].size())
    {
        sum -= pq[1].top(); // 依次减去横坐标，正好就是函数值
        pq[1].pop();
    }
    printOut(sum);
}

int main()
{
    run();
    return 0;
}

总结

  一道思维很深邃却又透露出套路的下凸函数的题目。这类题，首先你要发现下凸性质，其次你需要想清楚该怎么转移，更重要的，你需要想清楚在只保存拐点（关键点）的情况下如何计算出答案：是利用转移的性质边算边累计（如第一题）？还是利用函数性质最后来算（如这一题）？取决于你有没有观察出题目的性质了……一般来说，维护拐点通常都选择使用大根堆，把斜率大于 0$0$$0$ 的点给删去了（至少我做的唯一两道题是这样），如果遇到树（比如这道题），可以用可并堆。两个（下）凸函数相加后还是凸函数，且可能还满足某些别的性质（比如这道题）。