9pts & 已交换 求助

P4513 小白逛公园

1Stone @ 2022-10-06 14:43:12

思路有点奇怪,考虑把查询区间拆分成若干极大区间,最后用O(log^2 n)暴力统计答案,没有TLE,请问是思路太离谱了吗

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define mid ((l + r) >> 1)
#define lch (R << 1)
#define rch ((R << 1) | 1)
ll All[2000005], Max[2000005], F[2000005], E[2000005], N, T, cnt, val[500005], cho[500005];
void Pushup(ll R) {
    All[R] = All[lch] + All[rch];
    Max[R] = max(max(Max[lch], Max[rch]), E[lch] + F[rch]);
    F[R] = max(F[lch], All[lch] + F[rch]);
    E[R] = max(E[rch], All[rch] + E[rch]);
}
void Build(ll R, ll l, ll r) {
    if(l == r){Max[R] = F[R] = E[R] = All[R] = val[l]; return;}
    Build(lch, l, mid);
    Build(rch, mid + 1, r);
    Pushup(R);
}
void Update(ll R, ll l, ll r, ll k, ll v) {
    if(l == r) {
        Max[R] = F[R] = E[R] = All[R] = v;
        return;
    }
    if(k <= mid) Update(lch, l, mid, k, v);
    else Update(rch, mid + 1, r, k, v);
    Pushup(R);
}
void Query(ll R, ll l, ll r, ll ql, ll qr) {
    if(l >= ql && r <= qr) {
        cho[++cnt] = R;
        return; 
    }
    if(mid >= ql) Query(lch, l, mid, ql, qr);
    if(mid + 1 <= qr) Query(rch, mid + 1, r, ql, qr);
}
ll Ans() {
    ll ans = -1e15;
    for(int i = 1; i <= cnt; i++) ans = max(ans, Max[cho[i]]);
    for(int i = 1; i < cnt; i++) {
        ll Sum = 0;
        for(int j = i + 1; j <= cnt; j++) {
            ans = max(ans, E[cho[i]] + Sum + F[cho[j]]);
            Sum += All[cho[j]];
        }
    }
    return ans;
}
int main()
{
    cin >> N >> T;
    for(int i = 1; i <= N; i++) cin >> val[i];
    Build(1, 1, N);
    while(T--) {
        cnt = 0;
        ll op, x, y;
        cin >> op >> x >> y;
        if(op & 1) {
            if(x > y) swap(x, y);
            Query(1, 1, N, x, y);
            cout << Ans() <<'\n';
        }
        else {
            Update(1, 1, N, x, y);

        }
    }

    return 0;
}

by 1Stone @ 2022-10-06 14:45:50

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define mid ((l + r) >> 1)
#define lch (R << 1)
#define rch ((R << 1) | 1)
ll All[2000005], Max[2000005], F[2000005], E[2000005], N, T, cnt, val[500005], cho[500005];
//E表示区间最大后缀,F表示区间最大前缀,All为区间和, Max为区间最大子段和 
void Pushup(ll R) {
    All[R] = All[lch] + All[rch];
    Max[R] = max(max(Max[lch], Max[rch]), E[lch] + F[rch]);
    F[R] = max(F[lch], All[lch] + F[rch]);
    E[R] = max(E[rch], All[rch] + E[rch]);
}
void Build(ll R, ll l, ll r) {
    if(l == r){Max[R] = F[R] = E[R] = All[R] = val[l]; return;}
    Build(lch, l, mid);
    Build(rch, mid + 1, r);
    Pushup(R);
}
void Update(ll R, ll l, ll r, ll k, ll v) {
    if(l == r) {
        Max[R] = F[R] = E[R] = All[R] = v;
        return;
    }
    if(k <= mid) Update(lch, l, mid, k, v);
    else Update(rch, mid + 1, r, k, v);
    Pushup(R);
}
void Query(ll R, ll l, ll r, ll ql, ll qr) {
    if(l >= ql && r <= qr) {
        cho[++cnt] = R;
        return; 
    }
    if(mid >= ql) Query(lch, l, mid, ql, qr);
    if(mid + 1 <= qr) Query(rch, mid + 1, r, ql, qr);
}
ll Ans() {
    ll ans = -1e15;
    for(int i = 1; i <= cnt; i++) ans = max(ans, Max[cho[i]]);
    for(int i = 1; i < cnt; i++) {
        ll Sum = 0;
        for(int j = i + 1; j <= cnt; j++) {
            ans = max(ans, E[cho[i]] + Sum + F[cho[j]]);
            Sum += All[cho[j]];
        }
    }
    return ans;
}
int main()
{
    cin >> N >> T;
    for(int i = 1; i <= N; i++) cin >> val[i];
    Build(1, 1, N);
    while(T--) {
        cnt = 0;
        ll op, x, y;
        cin >> op >> x >> y;
        if(op & 1) {
            if(x > y) swap(x, y);
            Query(1, 1, N, x, y);
            cout << Ans() <<'\n';
        }
        else {
            Update(1, 1, N, x, y);

        }
    }

    return 0;
}

by 1Stone @ 2022-10-06 14:49:17

已AC,Pushup内容手残打错了,此帖完结


|