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内容手残打错了,此帖完结