题解：Team Building 解题思路与代码解析

问题核心分析

本题要求通过优化雇佣程序员的顺序，最大化团队实力，并处理动态更新技能值的查询。团队实力由所有成员的工作效率之和决定，而工作效率和动力会随雇佣顺序动态变化：

1. 新成员加入时，工作效率和动力初始为 $0$；
2. 之前雇佣的成员工作效率增加自身动力值；
3. 之前雇佣的成员动力值增加新成员的技能水平 $s_i$。

需计算初始状态及 $Q$ 次更新后，最优雇佣顺序下的最大团队实力。

核心思路

1. 数学建模团队实力：
   通过推导可知，团队实力可表示为技能值的二次函数组合。设雇佣顺序为 $p_1, p_2, \ldots, p_N$，则总实力为：

   $$\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} (j-i-1) \cdot s_{p_i} \cdot s_{p_j} $$

   该式可转化为基于技能值排序的多项式计算问题。

2. 最优排序策略：
   为最大化实力，技能值应按 升序 排列（通过不等式证明，相邻元素交换时升序更优）。

3. 动态维护与查询：
   使用平衡树（Treap）维护有序的技能值集合，支持高效插入、删除和更新操作。通过多项式表示每个元素对总实力的贡献，实现 $O(\log N)$ 时间复杂度的更新与查询。

代码实现解析

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;  // 适配 5×10^5 规模数据

int n, q, s[N], id[N], rt0, rt1;  // rt0、rt1 为两个平衡树根节点

// 快速读入优化
inline void read(int &ret) {
    ret = 0;
    int ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) ret = ret * 10 + (ch ^ 48), ch = getchar();
}

// 多项式结构：表示 a2·x² + a1·x + a0
struct poly {
    ll a2, a1, a0;
    ll calc(int x) {  // 计算多项式在 x 处的值
        return a2 * x * x + a1 * x + a0;
    }
    poly shift(int k) {  // 多项式平移：x → x + k
        return {a2, a2 * k * 2 + a1, a2 * k * k + a1 * k + a0};
    }
} I;  // 基础多项式，用于计算技能值贡献

// 多项式加法
poly operator + (const poly &a, const poly &b) {
    return {a.a2 + b.a2, a.a1 + b.a1, a.a0 + b.a0};
}

// 多项式乘以常数
poly operator * (const poly &a, const int k) {
    return {a.a2 * k, a.a1 * k, a.a0 * k};
}

mt19937 rnd(time(0));  // 随机数生成器，用于平衡树

// 平衡树节点结构
struct node {
    poly s, c;  // s：子树总贡献多项式；c：当前节点贡献多项式
    unsigned rn;  // 随机优先级
    int ls, rs, tg, sz;  // 左右子树、延迟标记、子树大小
    void addtag(int k) {  // 应用平移标记（子树整体后移 k 位）
        tg += k, s = s.shift(k), c = c.shift(k);
    }
} t[N];
int tot;  // 节点计数

// 创建新节点
int newnode(poly x) {
    t[++tot] = {x, x, rnd(), 0, 0, 0, 1};
    return tot;
}

// 上传子树信息
void pushup(int x) {
    t[x].sz = 1 + t[t[x].ls].sz + t[t[x].rs].sz;
    // 计算子树总贡献：左子树 + 当前节点（偏移左子树大小） + 右子树（偏移左子树+1）
    t[x].s = t[t[x].ls].s + t[x].c.shift(t[t[x].ls].sz) + t[t[x].rs].s.shift(t[t[x].ls].sz + 1);
}

// 下传延迟标记
void pushdown(int x) {
    if (!t[x].tg) return;
    if (t[x].ls) t[t[x].ls].addtag(t[x].tg);
    if (t[x].rs) t[t[x].rs].addtag(t[x].tg);
    t[x].tg = 0;
}

// 按 (s[x], x) 分裂平衡树
void split(int x, pair<int, int> p, int &l, int &r) {
    if (!x) { l = r = 0; return; }
    pushdown(x);
    if (make_pair(s[x], x) <= p)
        l = x, split(t[x].rs, p, t[l].rs, r);
    else
        r = x, split(t[x].ls, p, l, t[r].ls);
    pushup(x);
}

// 按子树大小分裂平衡树
void splsz(int x, int p, int &l, int &r) {
    if (!x) { l = r = 0; return; }
    pushdown(x);
    if (t[t[x].ls].sz + 1 <= p)
        l = x, splsz(t[x].rs, p, t[l].rs, r);
    else
        r = x, splsz(t[x].ls, p - t[t[x].ls].sz - 1, l, t[r].ls);
    pushup(x);
}

// 合并两个平衡树
int merge(int x, int y) {
    if (!x || !y) return x | y;
    pushdown(x), pushdown(y);
    if (t[x].rn <= t[y].rn) {
        t[x].rs = merge(t[x].rs, y);
        pushup(x);
        return x;
    } else {
        t[y].ls = merge(x, t[y].ls);
        pushup(y);
        return y;
    }
}

int main() {
    read(n), read(q);
    I = {-1, n + 1, -n};  // 初始化基础多项式，用于计算技能值贡献

    // 初始化节点
    for (int i = 1; i <= n; ++i) {
        read(s[i]);
        newnode(I * s[i]);  // 每个节点的贡献多项式为 I·s[i]
    }

    // 按技能值升序排序（相同技能值按编号升序）
    iota(id + 1, id + n + 1, 1);
    sort(id + 1, id + n + 1, [&](int x, int y) {
        return s[x] < s[y] || (s[x] == s[y] && x < y);
    });

    // 将排序后的节点交替放入两个平衡树（优化合并效率）
    for (int i = 1; i <= n; ++i) {
        if (i & 1) rt0 = merge(rt0, id[i]);
        else rt1 = merge(rt1, id[i]);
    }

    // 初始状态的最大团队实力
    printf("%lld\n", (t[rt0].s + t[rt1].s).calc(1));

    // 处理 Q 次更新
    for (int x, y; q--;) {
        read(x), read(y);
        int rta, rtb, rtc, rtd, rte;

        // 从两个平衡树中删除旧技能值的节点
        split(rt0, {s[x], x}, rta, rtb);
        split(rt1, {s[x], x}, rtc, rtd);
        split(rta, {s[x], x - 1}, rta, rte);
        if (!rte) split(rtc, {s[x], x - 1}, rtc, rte);

        // 更新技能值并重新插入节点
        swap(rtb, rtd);
        rt0 = merge(rta, rtb), rt1 = merge(rtc, rtd);
        t[rte].c = t[rte].s = I * y;  // 更新多项式为新技能值
        s[x] = y;

        // 将更新后的节点插入合适位置
        split(rt0, {s[x], x - 1}, rta, rtb);
        split(rt1, {s[x], x - 1}, rtc, rtd);
        if (t[rta].sz == t[rtc].sz) rta = merge(rta, rte);
        else rtc = merge(rtc, rte);

        // 合并平衡树并输出当前最大实力
        swap(rtb, rtd);
        rt0 = merge(rta, rtb), rt1 = merge(rtc, rtd);
        printf("%lld\n", (t[rt0].s + t[rt1].s).calc(1));
    }

    return 0;
}

关键逻辑说明

1. 多项式建模：
   每个技能值 $s_i$ 对总实力的贡献用二次多项式表示，通过平移操作（shift）处理位置变化对贡献的影响，避免重新计算整个序列。

2. 平衡树维护：
   使用 Treap（树堆）维护技能值的升序排列，支持高效的插入、删除和范围平移（通过延迟标记 tg）。将序列分为两个平衡树交替存储，优化合并操作效率。

3. 动态更新处理：
   每次更新技能值时，先从平衡树中删除旧值节点，更新多项式后重新插入正确位置，确保序列始终有序，从而维持最优解。

4. 复杂度分析：
   初始化排序为 $O(N \log N)$，每次更新涉及 $O(\log N)$ 次平衡树操作，总复杂度为 $O((N + Q) \log N)$，适配 $N \leq 5 \times 10^5$ 和 $Q \leq 10^5$ 的数据规模。

总结

该解法通过数学建模将团队实力转化为多项式计算，结合平衡树动态维护最优排序，高效处理初始状态和更新查询，核心是利用多项式平移和平衡树特性实现线性时间复杂度的动态优化。