2021-2022 ACM-ICPC Latin American Regional Programming Contest D Daily Turnovers

题目描述

https://codeforces.com/gym/103640/problem/D

简要题意：给定一个长度为 $n$ 的序列 $a_i$，定义合法区间 $[l,r]$ 为区间 $[l,r]$ 的所有前缀和都大于等于 $0$，现在再给一个数 $x$，求选择恰好一个位置将其加上 $x$ 后序列 $a_i$ 的合法区间的数量的最大值

$n\le 5\times 10^5$

Solution

我们首先考虑不加 $x$ 的情况，令 $s_i$ 表示前缀和，我们枚举区间左端点 $l$，求极长的右端点 $r$，容易得到 $r$ 为第一个满足 $s_r<s_{l-1}$ 的点，左端点 $l$ 的贡献为 $r-l$，给定 $l$ 找对应的 $r$ 可以用线段树来实现

我们考虑加上 $x$，不妨先考虑 $x$ 大于等于 $0$ 的情况。$x$ 大于等于 $0$ 意味着每个区间都是向右拓展的。同时我们发现因为是前缀和所以 $x$ 的作用是向右延伸的，如果想要影响区间 $[l,r]$，那么 $x$ 一定要作用在 $[l,r]$，且 $x$ 作用在 $[l,r]$ 内的任何一个位置都是一样的，那么我们的做法也就呼之欲出了，我们直接枚举所有的区间 $[l,r]$，求 $x$ 作用在区间内的答案的增量，这里相当于是一个区间加，我们差分之后求最大值即可

$x$ 小于 $0$ 则会麻烦一些，首先我们发现 $x$ 作用在 $[l,r]$ 内的不同位置的影响是不一样的，不过其无论如何 $r$ 都是减少的，我们考虑从右向左做扫描线，对于每个区间我们在 $r$ 加入，在 $l$ 删除，然后用权值线段树维护右端点 $r$ 的变化即可，另外还有一些细节

时间复杂度 $O(n\log n)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#define maxn 500010
#define INF 1000000000000000000
#define ll long long
using namespace std;

int n, m, a[maxn];
ll s[maxn];

#define lc i << 1
#define rc i << 1 | 1
namespace Seg1 { 
    ll T[maxn * 4];

    inline void maintain(int i) { T[i] = min(T[lc], T[rc]); }

    void build(int i, int l, int r) {
        if (l == r) return T[i] = s[l], void();
        int m = l + r >> 1;
        build(lc, l, m); build(rc, m + 1, r);
        maintain(i); 
    }

    int query(int i, int l, int r, int L, int R, ll v) {
        if (l > R || r < L) return 0;
        if (L <= l && r <= R && T[i] >= v) return 0;
        if (l == r) return T[i] < v ? l : 0;
        int m = l + r >> 1, ls = query(lc, l, m, L, R, v);
        if (ls) return ls;
        else return query(rc, m + 1, r, L, R, v);
    }
}

namespace Seg2 {
    struct Seg {
        ll v; int cnt;
        int cov;
    } T[maxn * 4]; 

    inline void maintain(int i) {
        T[i].cnt = T[lc].cnt + T[rc].cnt;
        T[i].v = T[lc].v + T[rc].v;
    }

    inline void Update(int i, int cov) {
        T[i].v = 1ll * T[i].cnt * cov;
        T[i].cov = cov;
    }

    inline void pushdown(int i) {
        int &cov = T[i].cov; if (!cov) return ;
        Update(lc, cov); Update(rc, cov);
        cov = 0; 
    }

    void update_v(int i, int l, int r, int L, int R, int v) {
        if (l > R || r < L) return ;
        if (L <= l && r <= R) return Update(i, v);
        int m = l + r >> 1; pushdown(i);
        update_v(lc, l, m, L, R, v); update_v(rc, m + 1, r, L, R, v);
        maintain(i);
    }

    void update_cnt(int i, int l, int r, int k, int cnt, int v) {
        if (l == r) return T[i].cnt += cnt, T[i].v += v, void();
        int m = l + r >> 1; pushdown(i); 
        if (k <= m) update_cnt(lc, l, m, k, cnt, v);
        else update_cnt(rc, m + 1, r, k, cnt, v);
        maintain(i);
    }
}


ll d[maxn];
vector<int> A[maxn];
void work0() {
    ll ans = 0; s[n + 1] = -INF; Seg1::build(1, 0, n + 1);
    for (int i = 0; i < n; ++i) {
        int t = Seg1::query(1, 0, n + 1, i + 1, n + 1, s[i]);
        ans += t - i - 1; A[t].push_back(i);
    } 
    for (int i = 1; i <= n; ++i) 
        for (auto t : A[i]) {
            int v = Seg1::query(1, 0, n + 1, t + 1, n + 1, s[t] - m) - i;
            d[t + 1] += v; d[i + 1] -= v;
        }
    for (int i = 1; i <= n; ++i) d[i] += d[i - 1];
    cout << ans + *max_element(d + 1, d + n + 1) << "\n";
}

ll b[maxn]; int cnt;
void init_hash() {
    for (int i = 0; i <= n; ++i) b[i + 1] = s[i]; 
    sort(b + 1, b + n + 2); cnt = unique(b + 1, b + n + 2) - b - 1;
    for (int i = 0; i <= n; ++i) s[i] = lower_bound(b + 1, b + cnt + 1, s[i]) - b; 
}

int nxt1[maxn], nxt2[maxn];
vector<pair<int, int>> B[maxn];

void work1() {
    ll res = 0, ans = -INF; s[n + 1] = -INF; Seg1::build(1, 0, n + 1);
    for (int i = 0; i < n; ++i) {
        int t = Seg1::query(1, 0, n + 1, i + 1, n + 1, s[i]);
        res += t - i - 1; B[i + 1].emplace_back(i, -1); B[t].emplace_back(i, 1);
        nxt1[i] = t; 
        nxt2[i] = Seg1::query(1, 0, n + 1, i + 1, n + 1, s[i] - m); 
    } init_hash();
    for (auto [k, opt] : B[n + 1]) {
        Seg2::update_cnt(1, 1, cnt, s[k], 1, nxt1[k]);
        res -= nxt1[k]; 
    }
    for (int i = n; i; --i) {
        int t = upper_bound(b + 1, b + cnt + 1, b[s[i]] + m) - b;
        Seg2::update_v(1, 1, cnt, t, cnt, i);
        ans = max(ans, res + Seg2::T[1].v); 
        for (auto [k, opt] : B[i]) {
            Seg2::update_cnt(1, 1, cnt, s[k], opt, opt > 0 ? i : -nxt2[k]);
            res += -opt * nxt1[k];
        }
    } cout << ans << "\n";
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> m >> n; 
    for (int i = 1; i <= n; ++i) cin >> a[i], s[i] = s[i - 1] + a[i];
    if (m >= 0) work0();
    else work1(); 
    return 0;
}