t6

wuhudsm

2024-12-01 22:10:46

发布于：浙江

5阅读

0回复

0点赞

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <climits>
using namespace std;

const int N = 500010;
long long a[N];
long long dp[N];
vector<long long> pp;
int n;

struct Node {
int l, r;
long long max;

Node() : l(0), r(0), max(LLONG_MIN) {}  
Node(int l, int r, long long max) : l(l), r(r), max(max) {}

};

Node tr[4 * N];
const long long INF = LLONG_MIN;

void build(int u, int l, int r);
void pushup(int u);
void update(int u, int l, int r, long long x);
long long query(int u, int l, int r);
int get(const vector<long long>& a, long long val);

void build(int u, int l, int r) {
if (l == r) {
tr[u] = Node(l, r, INF);
} else {
int mid = (l + r) / 2;
tr[u] = Node(l, r, INF);
build(u * 2, l, mid);
build(u * 2 + 1, mid + 1, r);
pushup(u);
}
}

void pushup(int u) {
tr[u].max = max(tr[u * 2].max, tr[u * 2 + 1].max);
}

void update(int u, int l, int r, long long x) {
if (tr[u].l >= l && tr[u].r <= r) {
if (x > tr[u].max) {
tr[u].max = x;
}
} else {
int mid = (tr[u].l + tr[u].r) / 2;
if (l <= mid) update(u * 2, l, r, x);
if (r > mid) update(u * 2 + 1, l, r, x);
pushup(u);
}
}

long long query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].max;
else {
int mid = (tr[u].l + tr[u].r) / 2;
long long max_val = INF;
if (l <= mid) max_val = max(max_val, query(u * 2, l, r));
if (r > mid) max_val = max(max_val, query(u * 2 + 1, l, r));
return max_val;
}
}

int get(const vector<long long>& a, long long val) {
int l = 0, r = a.size() - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (a[mid] <= val) l = mid;
else r = mid - 1;
}
return l;
}

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

cin >> n;
long long sum = 0;
pp.push_back(0);  
for (int i = 1; i <= n; i++) {
    cin >> a[i];
    sum += a[i];
    pp.push_back(sum);
}

set<long long> pp_set(pp.begin(), pp.end());
pp.assign(pp_set.begin(), pp_set.end());  // 去重并排序

build(1, 1, pp.size());

int t = get(pp, 0) + 1;
update(1, t, t, 0);

sum = 0;
dp[0] = 0;
for (int i = 1; i <= n; i++) {
    dp[i] = INF;
    sum += a[i];
    int id = get(pp, sum) + 1;  // 离散化下标

    // 查找最大值
    long long max_val = INF;
    if (id - 1 > 0) max_val = query(1, 1, id - 1);
    if (max_val != INF) dp[i] = max(max_val + i, dp[i]);

    if (a[i] > 0) dp[i] = max(dp[i - 1] + 1, dp[i]);
    if (a[i] < 0) dp[i] = max(dp[i - 1] - 1, dp[i]);
    if (a[i] == 0) dp[i] = max(dp[i - 1], dp[i]);

    update(1, id, id, dp[i] - i);
}

cout << dp[n] << endl;

return 0;

}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论