{\rtf1\ansi\ansicpg1250\deff0\deflang1048{\fonttbl{\f0\fswiss\fcharset238{\*\fname Arial;}Arial CE;}}
{\*\generator Msftedit 5.41.21.2508;}\viewkind4\uc1\pard\f0\fs20 #include <stdio.h>\par
#include <vector>\par
using namespace std;\par
\par
typedef long long ll;\par
struct un_nod\par
\{\par
\tab ll s_st, s_dr, s_max, s_tot;\par
\};\par
\par
int n, pos, val, seq_start, seq_end;\par
ll maxim, dreapta;\par
vector<un_nod> arb;\par
\par
void solve();\par
void update(int, int, int);\par
void query(int, int, int);\par
inline ll max(ll, ll);\par
inline ll max(ll, ll, ll);\par
\par
int main()\par
\{\par
\tab solve();\par
\tab return 0;\par
\}\par
\par
void solve()\par
\{\par
\tab int m, x, y, z;\par
\tab FILE *fin = fopen("maxq.in", "r");\par
\tab FILE *fout = fopen("maxq.out", "w");\par
\tab fscanf(fin, "%d", &n);\par
\tab arb.resize(4 * n+1000);\par
\par
\tab for (pos = 1; pos <= n; ++pos)\par
\tab\{\par
\tab\tab fscanf(fin, "%d", &val);\par
\tab\tab update(1, 1, n);\par
\tab\}\par
\par
\tab fscanf(fin, "%d", &m);\par
\tab for (; m; --m)\par
\tab\{\par
\tab\tab fscanf(fin, "%d%d%d", &x, &y, &z);\par
\par
\tab\tab if (x)\par
\tab\tab\{\par
\tab\tab\tab seq_start = y + 1;\par
\tab\tab\tab seq_end = z + 1;\par
\tab\tab\tab maxim = -(1<<30);\par
\tab\tab\tab dreapta = -(1<<30);\par
\tab\tab\tab query(1, 1, n);\par
\tab\tab\tab fprintf(fout, "%lld\\n", maxim);\par
\tab\tab\}\par
\tab\tab else\par
\tab\tab\{\par
\tab\tab\tab\par
\tab\tab\tab pos = y + 1;\par
\tab\tab\tab val = z;\par
\tab\tab\tab update(1, 1, n);\par
\tab\tab\}\par
\tab\}\par
\par
\tab fclose(fin);\par
\tab fclose(fout);\par
\}\par
\par
\par
\par
void query(int nod, int st, int dr)\par
\{\par
\tab if (seq_start <= st && dr <= seq_end)\par
\tab\{\par
\tab\tab maxim = max(maxim, arb[nod].s_max, dreapta + arb[nod].s_st);\par
\tab\tab dreapta = max(arb[nod].s_dr, dreapta + arb[nod].s_tot);\par
\tab\}\par
\tab else\par
\tab\{\par
\tab\tab int mid = (st + dr) / 2;\par
\tab\tab if (seq_start <= mid)\par
\tab\tab\{\par
\tab\tab\tab query(2 * nod, st, mid);\par
\tab\tab\}\par
\tab\tab if (mid < seq_end)\par
\tab\tab\{\par
\tab\tab\tab query(2 * nod + 1, mid + 1, dr);\par
\tab\tab\}\par
\tab\}\par
\}\par
\par
inline ll max(ll a, ll b)\par
\{\par
\tab return ((a > b) ? a : b);\par
\}\par
\par
inline ll max(ll a, ll b, ll c)\par
\{\par
\tab return ((a > b) ? ((a > c) ? a : c) : ((b > c) ? b : c));\par
\}\par
}