acwing 245 can you answer these questions

Title Link

Title Description:

Given A sequence A with length N and M instructions, each instruction may be one of the following two:

1. "1 x y", the maximum continuous subsegment sum in the query interval [x,y], i.e

2. "2 x y", change A[x] to y.

For each query instruction, an integer is output to represent the answer.

Train of thought:

First of all, it can be seen that this is an interval query, single point update, line tree. The topic requires that the maximum continuous fields and can maintain four variables with line tree. I can write the structure of line tree directly

struct p{
	ll l, r, lmax, rmax, max, sum;
	void init() {
		this->lmax = this->max = this->rmax = -inf;
		this->sum = 0;
	}
} ;

lmax: the maximum continuous field and starting from the leftmost end

rmax: same as above, the largest continuous field and

max: the maximum continuous field and

sum: interval and

Think about their connection. It's very simple.

  1. Interval sum is the sum of (the interval sum of left and right subintervals)
  2. lmax is the maximum value of (lmax of left interval) and (sum of left interval and right lmax) (as long as the left side and the left side are all part of the right side)
  3. rmax is the maximum of (right rmax) and (right rmax and left rmax)
  4. max is the maximum of (maximum value of left interval) and (maximum value of right interval) and (rmax of left interval + lmax of right interval)

In fact, it's an interval merger

There is a small problem. When querying, you need to use the maximum value of the left and right intervals, rmax of the left interval, and lmax of the right interval. However, there can only be one return value of a function, so you can return a structure type, write the above information into the structure and return it. Before each return, you can update the lmax, rmax, max, sum values together However, when a single point is updated, it should also be updated in the backtracking

The final result is a structure, and its max attribute is the answer

Code:

#include <bits/stdc++.h>
#define mem(a, b) memset(a, b, sizeof a)
#pragma warning (disable:6031)
#pragma warning (disable:4996)
#define inf 0x3f3f3f3f
using namespace std;
const int N = 310;
typedef long long ll;
struct p{
	ll l, r, lmax, rmax, max, sum;
	void init() {
		this->lmax = this->max = this->rmax = -inf;
		this->sum = 0;
	}
} c[N * 4];
void build(ll l, ll r, ll k) {
	c[k].l = l;
	c[k].r = r;
	if (l == r) {
		scanf("%lld", &c[k].max);
		c[k].lmax = c[k].rmax = c[k].sum = c[k].max;
		return;
	}
	ll mid = (l + r) / 2;
	build(l, mid, k * 2);
	build(mid + 1, r, k * 2 + 1);
	c[k].lmax = max(c[k << 1].lmax, c[k << 1].sum + c[k << 1 | 1].lmax);
	c[k].rmax = max(c[k << 1 | 1].rmax, c[k << 1 | 1].sum + c[k << 1].rmax);
	c[k].sum = c[k << 1].sum + c[k << 1 | 1].sum;
	c[k].max = max(c[k << 1].max, max(c[k << 1 | 1].max, c[k << 1].rmax + c[k << 1 | 1].lmax));
}
void update(ll ind, ll k, ll d) {
	if (c[k].l == c[k].r) {
		c[k].lmax = c[k].max = c[k].rmax = c[k].sum = d;
		return;
	}
	ll mid = (c[k].l + c[k].r) / 2;
	if (ind <= mid) {
		update(ind, k * 2, d);
	}
	else update(ind, k * 2 + 1, d);
	c[k].sum = c[k << 1].sum + c[k << 1 | 1].sum;
	c[k].lmax = max(c[k << 1].lmax, c[k << 1].sum + c[k << 1 | 1].lmax);
	c[k].rmax = max(c[k << 1 | 1].rmax, c[k << 1 | 1].sum + c[k << 1].rmax);
	c[k].max = max(c[k << 1].max, max(c[k << 1 | 1].max, c[k << 1].rmax + c[k << 1 | 1].lmax));
}
p query(ll l, ll r, ll k) {
	if (c[k].l >= l && c[k].r <= r) {
		return c[k];
	}
	ll mid = (c[k].l + c[k].r) / 2;
	p res;
	p ta, tb;
	res.init();
	ta.init();
	tb.init();
	if (l <= mid) {
		ta = query(l, r, k << 1);
	}
	if (r > mid) {
		tb = query(l, r, k << 1 | 1);
	}
	res.sum = ta.sum + tb.sum;
	res.lmax = max(ta.lmax, ta.sum + tb.lmax);
	res.rmax = max(tb.rmax, tb.sum + ta.rmax);
	res.max = max(ta.max, max(tb.max, ta.rmax + tb.lmax));
	return res;
}
int main()
{
	ll n, m;
	scanf("%lld %lld", &n, &m);
	build(1, n, 1);
	while (m--) {
		int op;
		ll x, y;
		scanf("%d %lld %lld", &op, &x, &y);
		if (op == 1) {
			if (x > y)swap(x, y);
			printf("%lld\n", query(x, y, 1).max);
		}
		else {
			update(x, 1, y);
		}
	}
	return 0;
}

 

Published 148 original articles, won praise 11, visited 8577
Private letter follow

Tags: Attribute

Posted on Wed, 29 Jan 2020 22:02:03 -0800 by Azad