Codeforces 855 B Marvolo Gaunt's Ring

Codeforces 855 B Marvolo Gaunt's Ring

题目链接

题目大意:
给出三个数p,q,r,和一个n个数的数组a[],求 p·ai + q·aj + r·ak的最大值,其中1 ≤ i ≤ j ≤ k ≤ n.

发牢骚：
一开始没看到i,j,k有顺序关系然后wa了两发（难受）。过了之后一早起来发现wa了,原来最小值初始化小了（难受）。
直接掉rating了。

分析:
对于p，q，r三个数来说，如果与q相乘的aj 确定了那么ai必定在[1,j],ak必定在[j,n]。
如果q>=0，那么ai就是在[1,j]的最大值，如果q<0，则ai就是在[1,j]的最大值。ak同理。
因为给出的数组a不一定是单调序列所以不能二分查找,但n的范围是1e5,想快点查找就想到上rmq了（线段树貌似也行）。
然后可想而知就是预处理出a[]的rmq数组maxs[]和mins[]，然后枚举aj来确定ai和ak。
总时间复杂度是O(nlogn（rmq预处理）+n（枚举aj））
有个细节就是初始化ans时其值必须小于-3*1e18，因为p,q,r和a[]范围是1e-9--1e9，可想而知最小值为-3*1e18。

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<cmath>
#include<stack>
#define mod 1030
#define size 3
using namespace std;
typedef long long LL;
const int maxn = (LL)1e5 + 100;
const int maxm = 50000;
const LL inf = (LL)6 * LL(1e18);
const double eps = 1e-8;
int mp[maxn];
struct rmq {int maxs[maxn][20], mins[maxn][20];int n;void read(int _n) {n = _n;for (int i = 1; i <= n; i++) {scanf("%d", &mp[i]);maxs[i][0] = mp[i];mins[i][0] = mp[i];}}void pre() {//预处理->O(nlogn)  int top = (int)(log(n * 1.0) / log(2.0));for (int j = 1; j <= top; ++j)for (int i = 1; i <= n; ++i)if (i + (1 << j) - 1 <= n) {maxs[i][j] = max(maxs[i][j - 1], maxs[i + (1 << (j - 1))][j - 1]);mins[i][j] = min(mins[i][j - 1], mins[i + (1 << (j - 1))][j - 1]);}}int querymax(int i, int j) {int k = (int)log2(j - i + 1.0), l = j - (1 << k) + 1;return max(maxs[i][k], maxs[l][k]);}int querymin(int i, int j) {int k = (int)log2(j - i + 1.0), l = j - (1 << k) + 1;return min(mins[i][k], mins[l][k]);}
}rmqs;
int main() {LL p, q, r;int n;while (scanf("%d", &n) == 1) {scanf("%I64d%I64d%I64d", &p, &q, &r);ad(n);rmqs.pre();LL ans = -inf;for (int i = 1; i <= n; i++) {LL tmp = q*mp[i];if (p >= 0) tmp += p*(LL)rmqs.querymax(1, i);else tmp += p*(LL)rmqs.querymin(1, i);if (r >= 0) tmp += r*(LL)rmqs.querymax(i, n);else tmp += r*(LL)rmqs.querymin(i, n);ans = max(ans, tmp);}printf("%I64dn", ans);}
}