CF1691D 题解

· · 题解

CF1691D link

Rd795 题解滞销，帮帮我（误

首先对于这个式子，不难注意到左边的 \max 只有 O(n) 种取值，所以想到枚举最大值是一件很自然的事。

那么可以变成枚举一个最大值 (\mathrm{pos}, v)，然后记 \mathrm{minL} 和 \mathrm{maxR} 为它能向左向右最长能延申到的地方。

经典把 \sum_{i=L}^{R}a_i 拆成前缀和做，变成 s_R-s_{L-1}，式子右边由「和 L,R 有关」变成「和 L 有关」和「和 R 有关」两部分，可以直接单独对 L 和 R 考虑。

问题变成在 [\mathrm{minL}-1,\mathrm{pos}) 中找一个 s 最小的，在 [\mathrm{pos}, \mathrm{maxR}] 中找一个 s 最大的，这样能使 \mathrm{Sum} 尽可能大，换句话说使条件尽可能不成立。关于最大最小 st 表就可以完美解决。

问题变成如何对于一个 (\mathrm{pos}, v) 找 \mathrm{minL} 和 \mathrm{maxR}，是个经典问题。

可以考虑把这 n 个数用链表将相邻的两个数连在一起，然后从小到大枚举最大值，每次枚举完一个值，就把这个值删去，更新链表。

这样每个数在链表上的左右的数就是第一个大于（等于）它的值了，因为比它小都删掉了，换句话说它们直接确定了 \mathrm{minL}-1 和 \mathrm{maxR}+1。

关于一个小细节：如果两个数值相等的时候，枚举的时候是有序的，不能保证 \mathrm{minL} 和 \mathrm{maxR} 是严格大于自己的，换句话说此时其实还可以再往左右延申（因为是左右可能是等于自己的，等于的话就可以再延申）。但这并不会影响答案，因为一段区间如果能成为答案，它一定会在某次枚举的时候被统计到。为什么？留作思考题吧。

在码量上我已经赢太多了

// Problem: D. Max GEQ Sum
// From: Codeforces - CodeCraft-22 and Codeforces Round #795 (Div. 2)
// URL: https://codeforces.com/contest/1691/problem/D
// Time: 2022-05-31 22:35
// Author: lingfunny

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mxn = 2e5+10;

int n, a[mxn], tot, pos[mxn], lg[mxn], p[mxn], L[mxn], R[mxn];
LL s[mxn], mis[20][mxn], mxs[20][mxn];
inline LL Qmi(int L, int R) {
    int k = lg[R-L+1];
    return min(mis[k][L], mis[k][R-(1<<k)+1]);
}
inline LL Qmx(int L, int R) {
    int k = lg[R-L+1];
    return max(mxs[k][L], mxs[k][R-(1<<k)+1]);
}

inline void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", a+i), s[i] = s[i-1] + a[i], p[i] = i, L[i] = i-1, R[i] = i+1;
    for(int i = 1; i <= n; ++i) mis[0][i] = s[i-1];
    for(int i = 1; i <= n; ++i) mxs[0][i] = s[i];
    for(int i = 1; i <= lg[n]; ++i)
    for(int j = 1; j <= n - (1<<i) + 1; ++j)
    mis[i][j] = min(mis[i-1][j], mis[i-1][j+(1<<(i-1))]),
    mxs[i][j] = max(mxs[i-1][j], mxs[i-1][j+(1<<(i-1))]);
    sort(p+1, p+n+1, [&](int x, int y) { return a[x] < a[y]; });
    for(int i = 1; i <= n; ++i) {
        int u = p[i];
        R[L[u]] = R[u], L[R[u]] = L[u];
        if(a[u] < Qmx(u, R[u]-1) - Qmi(L[u]+1, u)) return puts("NO"), void();
    }
    puts("YES");
}

int main() {
    lg[0] = -1;
    for(int i = 1; i < mxn; ++i) lg[i] = lg[i>>1] + 1;
    int tt;
    scanf("%d", &tt);
    while(tt--) solve();
}