Can you answer these queries III?

Can you answer these queries III?
Can you answer these queries III?
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;
}
上一篇:P3372 【模板】线段树 1


下一篇:P1908 逆序对