Link

Description

给定 $n$ 个点 $i$ 到点 $i+1$ 的距离 $d[i]$,每个点有一个权值 $h[i]$。现在有 $m$ 组询问,每次询问 $[l,r]$ 内两点 $x, y$, 使得$2*(h_x + h_y) + dis(x,y)$ 最大。其中 $dis(x,y)$ 表示 $x$ 到 $y$ 的距离。

Sol

墙裂推荐的好题

首先它给你的个点之间的距离是个环状的,你要断环成链。

接下来你要考虑如何将 $2*(h_x + h_y) + dis(x,y)$ 最大化。先考虑将 $2*(h_x + h_y) $ 和 $dis(x,y)$ 分别最大化。

显然将他们两个分别最大化的情况下,最大化的结果的 $x,y$ 坐标很有可能不是同一对。

假如两个最大值你不好同时查,就换成把最大化一个东西,再最小化另外一个并把加法做成减法

绝活。

考虑 $dis(x, y)$ 怎么计算,设 $sum[]$ 是$d[]$ 的前缀和,那么 $dis(x,y) = sum[y] - sum[x]$

这个时候我们就是要让 $sum_y - sum_x + 2 * h_x + 2 * h_y$ 最大

套路:把跟同一个东西相关的东西一起处理

现在变成了:$sum_y + 2 * h_y - sum_x + 2 * h_x$ 最大。那就让 $sum_y + 2 * h_y$ 最大,$sum_x + 2 * h_y$ 最小

因为没有修改操作,RMQ问题就可以用ST表,也可以用线段树之类的。

但是考虑一个问题,这样子做有可能查到的这两个的最大最小的位置是同一个位置,这样不符合要求。所以当我们查到了两个相同的位置的时候,就在 $[l, pos - 1] $ 和 $[pos + 1, r]$ 中查一下最大最小的位置就可以了。其中 $pos$ 是第一查到的最大最小位置。

同时注意到刚才我们要查的是位置,所以维护RMQ信息的时候要维护的是RMQ的下标。

Code

我实现用的线段树,比较好懂。用魔力ae86快读以后吊打ST表做法。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 2e5 + 5;
const int inf = 1e18;

int n, m;
int d[SIZE], h[SIZE], sumMin[SIZE], sumMax[SIZE];

struct node {
    int l, r, maxx, minn;
} tree[SIZE << 2];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

inline int getMax(int x, int y)
{
    return sumMax[x] > sumMax[y] ? x : y;
}

inline int getMin(int x, int y)
{
    return sumMin[x] < sumMin[y] ? x : y;
}

#define lson(p) p << 1
#define rson(p) p << 1 | 1

inline void pushUp(int p)
{
    tree[p].maxx = getMax(tree[lson(p)].maxx, tree[rson(p)].maxx);
    tree[p].minn = getMin(tree[lson(p)].minn, tree[rson(p)].minn);
}

inline void build(int p, int l, int r)
{
    tree[p].l = l, tree[p].r = r;
    if (l == r) {
        tree[p].maxx = tree[p].minn = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(lson(p), l, mid); build(rson(p), mid + 1, r);
    pushUp(p);
}

inline int queryMax(int p, int l, int r)
{
    if (l <= tree[p].l && tree[p].r <= r) {
        return tree[p].maxx;
    }
    int mid = (tree[p].l + tree[p].r) >> 1, ans = 0;
    if (l <= mid) ans = queryMax(lson(p), l, r);
    if (r > mid) ans = getMax(queryMax(rson(p), l, r), ans);
    return ans;
}

inline int queryMin(int p, int l, int r)
{
    if (l <= tree[p].l && tree[p].r <= r) {
        return tree[p].minn;
    }
    int mid = (tree[p].l + tree[p].r) >> 1, ans = 0;
    if (l <= mid) ans = queryMin(lson(p), l, r);
    if (r > mid) ans = getMin(queryMin(rson(p), l, r), ans);
    return ans;
}

inline int calcMin(int l, int r)
{
    if (l > r) return 0;
    return queryMin(1, l, r);
}

inline int calcMax(int l, int r)
{
    if (l > r) return 0;
    return queryMax(1, l, r);
}

inline int solve(int l, int r)
{
    int minn = calcMin(l, r), maxx = calcMax(l, r);
    if (minn != maxx) return sumMax[maxx] - sumMin[minn];
    int minn2 = getMin(calcMin(l, minn - 1), calcMin(minn + 1, r));
    int maxx2 = getMax(calcMax(l, maxx - 1), calcMax(maxx + 1, r));
    return std::max(sumMax[maxx2] - sumMin[minn], sumMax[maxx] - sumMin[minn2]);
}

signed main()
{
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    n = read(), m = read();
    for (register int i = 1; i <= n; ++ i) {
        d[i % n + 1] = d[i % n + 1 + n] = read();
    }
    for (register int i = 1; i <= n; ++ i) {
        h[i] = h[i + n] = read();
    }    
    int sum = 0; sumMax[0] = -inf, sumMin[0] = inf;
    for (register int i = 1; i <= (n << 1); ++ i) {
        sum += d[i];
        sumMax[i] = sum + 2 * h[i];
        sumMin[i] = sum - 2 * h[i];
    }
    build(1, 1, 2 * n + 1);
    while (m --) {
        int l = read(), r = read();
        if (l <= r) printf("%lld\n", solve(r + 1, n + l - 1));
        else printf("%lld\n", solve(r + 1, l - 1));
    }
    return 0;
}
最后修改:2021 年 09 月 04 日
如果觉得我的文章对你有用,请随意赞赏