Sum Sum Max(数学+三分)

Sum Sum Max(数学+三分)

Sum Sum Max

[Link](F - Sum Sum Max (atcoder.jp))

题意

​ 给你长度为 m m m的数组 C C C，接下来给你 n n n组数，每组为 x i , y i x_i,y_i xi​,yi​，表示有 y i y_i yi​个 x i x_i xi​，这 n n n组数依次构成数组 C C C。 B B B数组是 C C C数组的前缀和， A A A数组是 B B B数组的前缀和，现在让你求 M a x ( A i ) Max(A_i) Max(Ai​)。

思路

设 z z z为 y y y的前缀和，则对于每一段数假设第 i i i段，应该为 [ z i − 1 + 1 , z i ] [z_{i-1}+1,z_i] [zi−1​+1,zi​]这个下标且这一段在 C C C中均为 x i x_i xi​，那么这一段对应的 B z i = B z i − 1 + y i × x i B_{z_i}=B_{z_{i-1}}+y_itimes x_i Bzi​​=Bzi−1​​+yi​×xi​，则 A z i = A z i − 1 + B z i − 1 × y i + x i × ( 1 + y i ) × y i / 2 A_{z_i} = A_{z_{i-1}}+B_{z_{i-1}} times y_i + x_itimes (1+y_i)times y_i / 2 Azi​​=Azi−1​​+Bzi−1​​×yi​+xi​×(1+yi​)×yi​/2，那么可以整理为 A z i = a x 2 + b x + c = f ( x ) A_{z_i}=ax^2+bx+c=f(x) Azi​​=ax2+bx+c=f(x)这种形式。

​ 分类来看

• a ≥ 0 age 0 a≥0 这个时候最大值只会在左右端点
• a < 0 alt 0 a<0 这个时候最大值是中间的某个点，设为 m r m_r mr​，则 f ( 1 ) < f ( 2 ) < . . . < f ( m r ) f(1)lt f(2)lt ...lt f(m_r) f(1)<f(2)<...<f(mr​)， f ( m r ) > f ( m 1 + 1 ) f(m_r)gt f(m_1+1) f(mr​)>f(m1​+1)，我们可以三分找到这个 m r m_r mr​

然后按顺序枚举每个区间，不断地更新 a , b , c a,b,c a,b,c即可，维护答案即可。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <unordered_map>
#include <cmath> 
#include <stack>
#include <iomanip>
#include <deque> 
#include <sstream>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
using LL = long long;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
LL n, m, k;
LL x, y;
LL a = 0, b = 0;
LL f(LL k) {return a + b * k + (1 + k) * k / 2 * x;
}
LL check(int l, int r) {while (l + 2 < r) {int m1 = l + r >> 1, m2 = m1 + 1;if (f(m1) < f(m2)) l = m1;else r = m2;}return f(l + 1);
}
int main() {ios::sync_with_stdio(false), cin.tie(0);int T;cin >> T;while (T -- ) {cin >> n >> m;a = 0, b = 0;LL res = -1e18;for (int i = 1; i <= n; i ++) {cin >> x >> y;if (x >= 0) {res = max(res, f(y));res = max(res, f(1));}else res = max(res, check(0, y + 1));a = f(y);b += x * y;}cout << res << endl;}return 0;
}