Can you answer these queries III?
代码
#include<iostream>
#define max(a,b) ((a)>(b))?(a):(b)
using namespace std;
const int maxn = 100005;
int n, m, x, y;
struct segmentTree
{
int l, r;
int lmax, rmax, sum, dat;
}tr[maxn << 2];
int a[maxn];
void up(int p)
{
tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
tr[p].lmax = max(tr[p << 1].lmax, tr[p << 1].sum + tr[p << 1 | 1].lmax);
tr[p].rmax = max(tr[p << 1 | 1].rmax, tr[p << 1 | 1].sum + tr[p << 1].rmax);
tr[p].dat = max(max(tr[p << 1].dat, tr[p << 1 | 1].dat), tr[p << 1].rmax + tr[p << 1 | 1].lmax);
}
void build(int p, int l, int r)
{
tr[p].l = l, tr[p].r = r;
if (l == r)
{
tr[p].dat = tr[p].sum = tr[p].lmax = tr[p].rmax = a[l];
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
up(p);
}
segmentTree query(int p, int l, int r, int ql, int qr)
{
if (ql <= l && qr >= r)
return tr[p];
int mid = (l + r) >> 1;
if (ql > mid)
return query(p << 1 | 1, mid + 1, r, ql, qr);
if (qr <= mid)
return query(p << 1, l, mid, ql, qr);
else
{
segmentTree ans, a, b;
a = query(p << 1, l, mid, ql, qr);
b = query(p << 1 | 1, mid + 1, r, ql, qr);
ans.sum = a.sum + b.sum;
ans.dat = max(a.dat, a.rmax + b.lmax);
ans.dat = max(ans.dat, b.dat);
ans.lmax = max(a.lmax, a.sum + b.lmax);
ans.rmax = max(b.rmax, b.sum + a.rmax);
return ans;
}
}
void change(int p, int x, int y)
{
int l = tr[p].l, r = tr[p].r;
if (l == r)
{
tr[p].dat= tr[p].lmax = tr[p].rmax = tr[p].sum = y;
return;
}
int mid = (l + r) >> 1;
if (l == x && l == r)
{
tr[p].dat = tr[p].lmax = tr[p].rmax = tr[p].sum = y;
up(p); return;
}
if (x <= mid) change(p<<1, x, y); else change(p<<1|1, x, y);
up(p);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int x, y,z;
build(1, 1, n);
cin >> m;
while(m--)
{
cin >> z;
if (z == 0)
{
cin >> x >> y;
change(1, x, y);
}
if (z == 1)
{
cin >> x >> y;
printf("%d\n", query(1, 1, n, x, y).dat);
}
}
return 0;
}