Stavo provando a risolvere il problema panama sum, ho creato 2 array entrambi con i valori invertiti ogni 2 semplicemente uno inverso all’altro (dall’array {2,3,6,4} creo {2,-3,6,-4} e {-2,3,-6,4} faccio due segment tree per restituire sotto array con la somma massima su questi 2 array e ogni volta controllo uno e l’altro e faccio il print del massimo dei 2, per gli update li cambio entrambi uno con il valore opposto all’altro.
Questo è il codice:
#define MAXN 100001
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ip;
typedef vector<int> vi;
ifstream in("input.txt");
// ofstream out("output.txt");
int N, Q;
vector<int> V;
struct node
{
int sum, pref, suff, best;
};
vector<node> arr(MAXN * 4);
vector<node> arri(MAXN * 4);
node combine(node a, node b)
{
node res;
res.sum = a.sum + b.sum;
res.pref = max(a.pref, a.sum + b.pref);
res.suff = max(b.suff, b.sum + a.suff);
res.best = max(a.suff + b.pref, max(a.best, b.best));
return res;
}
node makenode(int val)
{
node res;
res.sum = val;
res.pref = res.suff = res.best = max(0, val);
return res;
}
void build(int v, int nl, int nr, vector<node> &c)
{
if (nl == nr)
{
c[v] = makenode(V[nl]);
}
else
{
int nm = (nl + nr) / 2;
build(v * 2, nl, nm, c);
build(v * 2 + 1, nm + 1, nr, c);
c[v] = combine(c[v * 2], c[v * 2 + 1]);
}
}
void update(int v, int nl, int nr, int pos, int newval, vector<node> &c)
{
if (nl == nr)
c[v] = makenode(newval);
else
{
int nm = (nl + nr) / 2;
if (pos <= nm)
update(v * 2, nl, nm, pos, newval, c);
else
update(v * 2 + 1, nm + 1, nr, pos, newval, c);
c[v] = combine(c[v * 2], c[v * 2 + 1]);
}
}
node query(int v, int nl, int nr, int ql, int qr, vector<node> &c)
{
if (nl > qr || nr < ql)
return makenode(0);
if (nl >= ql && nr <= qr)
return c[v];
int nm = (nl + nr) / 2;
return combine(query(v * 2, nl, nm, ql, qr, c), query(v * 2 + 1, nm + 1, nr, ql, qr, c));
}
int main()
{
in >> N >> Q;
V.resize(N);
for (int i = 0; i < N; i++)
{
in >> V[i];
if (i % 2 == 1)
V[i] *= -1;
}
build(1, 0, N - 1, arr);
for (int i = 0; i < N; i++)
V[i] *= -1;
build(1, 0, N - 1, arri);
for (int i = 0; i < Q; i++)
{
int t;
in >> t;
if (t == 1)
{
int a, b;
in >> a >> b;
a--;
if (a % 2 == 1)
b *= -1;
update(1, 0, N - 1, a, b, arr);
b *= -1;
update(1, 0, N - 1, a, b, arri);
}
else
{
int l, r;
in >> l >> r;
l--;
r--;
node temp;
node temp2;
temp = query(1, 0, N - 1, l, r, arr);
temp2 = query(1, 0, N - 1, l, r, arri);
cout << max(temp.best, temp2.best) << "\n";
}
}
return 0;
}