AI秒杀？【测试AI】

原题链接：34572.划分区间

复仇者_零

2025-05-02 21:04:20

发布于：浙江

50阅读

0回复

0点赞

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG_INF = LLONG_MIN / 2;

struct Fenwick {
    int n;
    vector<ll> t;
    Fenwick(int _n): n(_n), t(n+1, NEG_INF) {}

    // 在位置 i 上更新：t[i] = max(t[i], v)
    void update(int i, ll v) {
        for (; i <= n; i += i & -i)
            t[i] = max(t[i], v);
    }
    // 查询前缀 [1..i] 的最大值
    ll query(int i) {
        ll r = NEG_INF;
        for (; i > 0; i -= i & -i)
            r = max(r, t[i]);
        return r;
    }
};

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

    int n;
    cin >> n;
    vector<ll> A(n+1, 0);
    for(int i = 1; i <= n; i++){
        cin >> A[i];
    }

    // 1) 计算前缀和
    vector<ll> S(n+1, 0);
    for(int i = 1; i <= n; i++){
        S[i] = S[i-1] + A[i];
    }

    // 2) 离散化所有前缀和
    vector<ll> comp = S;
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    int m = comp.size();

    // 3) 准备两个 Fenwick Tree：
    //    FT1 存 dp[j] - j，用于查询 s[j] < s[i] 的情况
    //    FT2 存 dp[j] + j，用于查询 s[j] > s[i] 的情况（反向离散后用前缀即可）
    Fenwick ft1(m), ft2(m);

    // 4) 存储相等前缀和时的最佳 dp 值
    vector<ll> best_eq(m+1, NEG_INF);

    auto get_id = [&](ll x){
        return int(lower_bound(comp.begin(), comp.end(), x) - comp.begin()) + 1;
    };

    vector<ll> dp(n+1, NEG_INF);
    dp[0] = 0;
    // 初始化 j=0 的状态
    int id0 = get_id(S[0]);
    best_eq[id0] = 0;
    ft1.update(id0, dp[0] - 0);
    // 对于 ft2，我们把离散坐标反过来：rev = m-id+1
    ft2.update(m - id0 + 1, dp[0] + 0);

    // 5) 按顺序计算 dp[i]
    for(int i = 1; i <= n; i++){
        int id = get_id(S[i]);
        // 情况1：存在 j<i 且 s[j] < s[i]
        ll v1 = ft1.query(id - 1);
        if (v1 > NEG_INF) v1 += i;

        // 情况2：存在 j<i 且 s[j] > s[i]
        ll v2 = ft2.query(m - (id + 1) + 1);
        if (v2 > NEG_INF) v2 -= i;
        
        // 情况3：存在 j<i 且 s[j] == s[i]
        ll v3 = best_eq[id];
        
        dp[i] = max({v1, v2, v3});

        // 更新三种结构
        best_eq[id] = max(best_eq[id], dp[i]);
        ft1.update(id, dp[i] - i);
        ft2.update(m - id + 1, dp[i] + i);
    }

    // 答案就是 dp[n]
    cout << dp[n] << "\n";

    return 0;
}