二元函数求和最大值问题（Innophone）题解

这道题的核心是通过合理选择常数 (a) 和 (b)，最大化二元函数 (f(x,y)) 对所有给定 ((x_i,y_i)) 的求和结果。解题关键在于将函数求和转化为可高效计算的数学模型，并利用排序、离散化和线段树（维护线性函数）优化求解过程。

一、题目分析与核心思路

1. 函数规则拆解

二元函数 (f(x,y)) 的定义可拆解为对每组 ((x_i,y_i)) 的贡献判断：

• 若 (a \leq x_i)：贡献为 (a)；
• 若 (a > x_i) 且 (b \leq y_i)：贡献为 (b)；
• 若 (a > x_i) 且 (b > y_i)：贡献为 (0)。

2. 求和公式转化

设满足 (a \leq x_i) 的组数为 (c)，满足 (a > x_i) 且 (b \leq y_i) 的组数为 (d)，则总求和为： [ \sum f(x_i,y_i) = a \cdot c + b \cdot d ] 其中 (c + d \leq n)（(c) 是“选 (a) 贡献”的数量，(d) 是“选 (b) 贡献”的数量）。

3. 关键观察

• 若固定 (a)，则 (c) 是 (x_i \geq a) 的组数，(d) 是 (x_i < a) 且 (y_i \geq b) 的组数；
• 对固定 (a)，(a \cdot c) 是定值，最大化总和只需最大化 (b \cdot d)（即选择 (b) 为某个 (y_i)，使 (d) 尽可能大）；
• 所有可能的 (a) 必然是某个 (x_i)（因 (x_i) 排序后，(a) 取非 (x_i) 值时，(c) 和 (d) 的计数不变），可通过排序 (x_i) 枚举所有有效 (a)。

二、算法设计与实现步骤

1. 预处理：排序与离散化

• 排序：将所有 ((x_i,y_i)) 按 (x_i) 升序排列，确保枚举 (a) 时可按顺序更新 (c)（(x_i \geq a) 的数量）；
• 离散化：因 (y_i) 范围可达 (10^9)，将 (y_i) 映射到小范围（1~tot，tot 为不同 (y_i) 的数量），方便线段树维护。

2. 线段树维护线性函数

线段树的核心作用是维护“(b \cdot d)”的最大值：

• 每个节点存储一个线性函数 (g(b) = k \cdot b)，其中 (k) 是“(y_i \geq b) 且未被 (a) 覆盖”的组数（即 (d)）；
• 当枚举 (a) 时，若某个 (x_i < a)，则该 (x_i) 对应的 (y_i) 需纳入 (b) 的计数范围，即在线段树中更新对应 (y_i) 位置的 (k)（+1）；
• 线段树支持快速查询当前所有 (b) 对应的 (g(b)) 最大值（即 (b \cdot d) 的最大值）。

3. 枚举与计算

按排序后的 (x_i) 枚举所有可能的 (a)（即 (a = x_i)）：

• 计算当前 (a) 对应的 (a \cdot c)（(c = n - i + 1)，因前 (i-1) 个 (x_i < a)）；
• 加上线段树查询到的 (b \cdot d) 最大值，更新全局答案；
• 将当前 (x_i) 对应的 (y_i) 纳入线段树（更新 (k)），为后续更小的 (a) 做准备。

三、完整代码实现

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pr pair<line, ll>
#define mk make_pair
#define fst first
#define snd second

// 快读优化
char buf[1048576], *p1 = buf, *p2 = buf, ubuf[1048576], *u = ubuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1048576,stdin),p1==p2)?EOF:*p1++)

const ll N = 1.5e5 + 5, inf = LONG_LONG_MAX;
ll n, m, tg[N << 2], lsh[N], tot, ans, now;  // tg:线段树懒标记；lsh:y的离散化数组

// 线性函数结构体：g(b) = a*b + b（此处变量名注意：a是系数，b是常数项）
struct line {
    ll a, b;
    friend line operator+(line a, line b) {  // 函数合并（系数和常数项分别相加）
        return {a.a + b.a, a.b + b.b};
    }
};

// 比较两个线性函数，返回在当前b下更大的函数及交点（交点后另一个函数更优）
inline pr maxf(line x, line y) {
    if (x.a < y.a || (x.a == y.a && x.b < y.b))
        swap(x, y);
    if (x.b >= y.b)  // x始终更优，交点为无穷大
        return mk(x, inf);
    // 计算交点：x.a*b + x.b = y.a*b + y.b → b = (y.b - x.b)/(x.a - y.a)
    return mk(y, (y.b - x.b) / (x.a - y.a));
}

// 线段树节点结构体：存储线性函数、有效区间（交点前当前函数更优）
struct KTT {
    line s;    // 节点维护的线性函数
    ll intr;   // 有效区间的右边界（超过后需拆分）
#define s(z) t[z].s
#define intr(z) t[z].intr
    // 节点合并：合并左右子节点的函数和有效区间
    friend KTT operator+(KTT x, KTT y) {
        KTT res;
        pr g;
        res.intr = min(x.intr, y.intr);  // 初始有效区间取两者最小值
        g = maxf(x.s, y.s);              // 比较两个函数，取当前更优的
        res.s = g.fst;
        res.intr = min(res.intr, g.snd); // 有效区间更新为更小的交点
        return res;
    }
} t[N << 2];

// 线段树pushup：合并子节点信息到父节点
inline void pushup(int k) {
    t[k] = t[k << 1] + t[k << 1 | 1];
}

// 线段树建树：初始化每个叶子节点为y离散化后对应的线性函数g(b)=1*b（k=1）
inline void build(ll k, ll l, ll r) {
    if (l == r) {
        intr(k) = inf;          // 叶子节点无交点，有效区间无穷大
        s(k) = {lsh[l], 0};     // 初始函数：系数为lsh[l]（b的取值），常数项0
        return;
    }
    ll mid = l + r >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    pushup(k);
}

// 线段树push：懒标记下传，更新函数和有效区间
inline void push(ll k, ll v) {
    tg[k] += v;                // 懒标记累加（表示b的偏移量）
    intr(k) -= v;              // 有效区间右边界随b偏移减小
    s(k).b += s(k).a * v;      // 函数常数项更新：a*b中的b偏移v，等价于常数项+a*v
}

// 线段树pushdown：将懒标记下传到子节点
inline void pushdown(ll k) {
    if (!tg[k]) return;
    push(k << 1, tg[k]);
    push(k << 1 | 1, tg[k]);
    tg[k] = 0;
}

// 线段树rebuild：拆分无效节点（有效区间小于0时，需重新合并子节点）
inline void rebuild(ll k) {
    if (intr(k) >= 0) return;  // 有效区间仍合法，无需拆分
    pushdown(k);               // 下传懒标记
    rebuild(k << 1);           // 递归处理子节点
    rebuild(k << 1 | 1);
    pushup(k);                 // 重新合并子节点信息
}

// 线段树区间更新：将[1, a[r].snd]（y<=当前y的范围）的函数系数+1（增加一个计数d）
inline void Add(ll k, ll x, ll y, ll v, ll l, ll r) {
    if (x <= l && r <= y) {
        push(k, v);
        rebuild(k);
        return;
    }
    ll mid = l + r >> 1;
    pushdown(k);
    if (mid >= x) Add(k << 1, x, y, v, l, mid);
    if (mid + 1 <= y) Add(k << 1 | 1, x, y, v, mid + 1, r);
    pushup(k);
}

// 线段树区间查询：查询[1, tot]的最优线性函数（即b*d的最大值）
inline KTT que(ll k, ll x, ll y, ll l, ll r) {
    if (x <= l && r <= y) return t[k];
    ll mid = l + r >> 1;
    pushdown(k);
    if (y <= mid) return que(k << 1, x, y, l, mid);
    if (mid < x) return que(k << 1 | 1, x, y, mid + 1, r);
    return que(k << 1, x, y, l, mid) + que(k << 1 | 1, x, y, mid + 1, r);
}

// 快读函数
inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * f;
}

pair<ll, ll> a[N];  // 存储(x_i, y_i)

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    n = now = read();  // now初始为n（c的初始值：所有x_i >= a）

    // 读入数据并收集y_i用于离散化
    for (ll i = 1; i <= n; i++) {
        a[i].fst = read();       // x_i
        lsh[++tot] = a[i].snd = read();  // y_i，同时存入lsh
    }

    // 排序与离散化
    sort(a + 1, a + n + 1);  // 按x_i升序排列
    sort(lsh + 1, lsh + tot + 1);  // 对y_i排序
    tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;  // 去重，得到离散化后的数据量
    for (ll i = 1; i <= n; i++) {
        // 将y_i映射到离散化后的索引（1~tot）
        a[i].snd = lower_bound(lsh + 1, lsh + tot + 1, a[i].snd) - lsh;
    }

    // 初始化线段树
    build(1, 1, tot);

    // 枚举所有可能的a（即x_i），计算最大总和
    for (ll i = 1, r; i <= n; i++) {
        // 当前a = a[i].fst，总和 = a*c + (b*d)最大值（线段树维护的s(1).b）
        ans = max(ans, now * a[i].fst + s(1).b);

        // 处理所有x_i = a[i].fst的组（避免重复枚举相同a）
        for (r = i; r <= n && a[i].fst == a[r].fst; r++) {
            now--;  // c减少1（该组x_i = a，后续a更小则x_i < a，不再计入c）
            // 将该组的y_i纳入线段树（更新d的计数）
            Add(1, 1, a[r].snd, 1, 1, tot);
        }
        i = r - 1;  // 跳过已处理的相同x_i的组
    }

    // 输出最大总和
    cout << ans;
    return 0;
}

四、算法复杂度分析

1. 时间复杂度：

   • 排序与离散化：(O(n\log n))（排序 (x_i) 和 (y_i)，离散化去重）；
   • 线段树操作：建树 (O(tot))（tot 是不同 (y_i) 的数量，(tot \leq n)），每次更新和查询 (O(\log tot))，共 (O(n\log n)) 次操作；
   • 总时间复杂度：(O(n\log n))，可处理 (n=1.5 \times 10^5) 的数据规模。

2. 空间复杂度：

   • 线段树占用 (O(4 \times tot)) 空间，离散化数组占用 (O(n)) 空间；
   • 总空间复杂度：(O(n))，符合题目内存要求。

五、关键优化点

1. 离散化：将大范围的 (y_i) 映射到小范围，避免线段树因数值过大导致空间浪费；
2. 线段树维护线性函数：将“(b \cdot d)”的最大值问题转化为线性函数的维护，通过合并函数和有效区间实现高效查询；
3. 批量处理相同 (x_i)：避免对相同 (a) 的重复枚举，减少冗余计算；
4. 懒标记与 rebuild：通过懒标记优化区间更新，rebuild 确保函数有效区间的正确性，平衡更新与查询效率。