“你动规无力，图论不稳，数据结构松散，贪心迟钝，没一样像样的，就你还想和我同台竞技，做你的美梦！今天这场比赛，就是要让你知道你是多么

的无能！！”

不训练，无以为战。有n项能力是ACM竞赛要求的，训练则能提升，忽略则会荒废。

这m天，你能做到如何。

Input

第一行两个整数n，m,分别表示有n项能力要求，共有m天。

第二行n个整数，第i个整数ai表示第i项能力的数值。

接下来m行，每行开始先读入一个整数si，表明这是一次询问还是一次能力变化。

si=0，表明这是一次询问，然后读入两个整数li,ri，表示询问在[li，ri]区间中任选一段连续序列，这段序列中所有能力值之和最大能是多少。

si=1，表明这是一次能力变化，然后读入两个整数xi,wi，表示第xi项能力变为了wi。

1≤n,m≤100000,−10000≤ai≤10000,1≤li≤ri≤n,1≤xi≤n,−10000≤wi≤10000

Output

有多少询问就输出多少行，每行输出一个整数，作为对该询问的回答。

Sample input and output

4 4

1 2 3 4

0 1 3

1 3 -3

0 2 4

0 3 3

6

4

-3

此题使用线段树解决。不过与一般的线段树不同，这道题需要用到4个sum变量。考虑每一个节点sequ[now]，令其和为sum，连接到其最左边的值的

子串的最大和为sum1，连接到其最右边的值的字串的最大和为sum2，另其连续字串的最大和为sum0。则有以下四个等式：

sequ[now].sum = sequ[2 *
now].sum + sequ[2 * now + 1].sum;

sequ[now].sum0 = max(sequ[2 *
now].sum2, max(sequ[2 * now].sum2 + sequ[2 *now + 1].sum1, max(sequ[2 *now + 1].sum1,max(sequ[2*now].su

m0,sequ[2*now+1].sum0))));

sequ[now].sum1 = max(sequ[2 *
now].sum1, sequ[2 * now].sum + sequ[2 *
now + 1].sum1);

sequ[now].sum2 = max(sequ[2 *
now + 1].sum2, sequ[2 * now + 1].sum + sequ[2 *now].sum2);

这样维护的线段树，就能得到每一个节点的各个最值。然后在询问时使用深搜，从下往上，用和更新时同样的思想，维护不断连接的区间的各个最值，

最后输出sum0，便是得到的最值。详见代码。

#include<iostream>

#include<algorithm>

#include<stack>

#include<stdio.h>

#define MAX_N 100005

#define MAX_M 100005

using namespace std;

struct node

{

	int left, right, sum0, sum1, sum2, sum;

	node()

	{

		sum0 = sum1 = sum2 = sum = 0;

	}

};

node sequ[4 * MAX_N + 1000];

stack<int> st;

void build(int x, int l, int r)

{

	sequ[x].left = l;

	sequ[x].right = r;

	if (l != r)

	{

		int k = (l + r) / 2;

		build(2 * x, l, k);

		build(2 * x + 1, k + 1, r);

	}

}

void update(int now, int n, int a)

{

	if (sequ[now].left == n&&sequ[now].right == n)

		sequ[now].sum = sequ[now].sum0 = sequ[now].sum1 = sequ[now].sum2 = a;

	else

	{

		int k = (sequ[now].left + sequ[now].right) / 2;

		if (k >= n)

			update(2 * now, n, a);

		else

			update(2 * now + 1, n, a);

		sequ[now].sum = sequ[2 * now].sum + sequ[2 * now + 1].sum;

		sequ[now].sum0 = max(sequ[2 * now].sum2, max(sequ[2 * now].sum2 + sequ[2 * now + 1].sum1, max(sequ[2 * now + 1].sum1

		,max(sequ[2*now].sum0,sequ[2*now+1].sum0))));

		sequ[now].sum1 = max(sequ[2 * now].sum1, sequ[2 * now].sum + sequ[2 * now + 1].sum1);

		sequ[now].sum2 = max(sequ[2 * now + 1].sum2, sequ[2 * now + 1].sum + sequ[2 * now].sum2);

	}

}

void ask(int l, int r, int now)

{

	if (sequ[now].left == l&&sequ[now].right == r)

		st.push(now);

	else

	{

		int k = (sequ[now].right + sequ[now].left) / 2;

		if (k < l)

			ask(l, r, now * 2 + 1);

		else if (k >= r)

			ask(l, r, now * 2);

		else

		{

			ask(l, k, now * 2);

			ask(k + 1, r, now * 2 + 1);

		}

	}

}

int answer()

{

	int sumT0 = 0, sumT1 = 0, sumT2 = 0, sumT = 0;

	int nr, nl;

	sumT0 = sequ[st.top()].sum0;

	sumT1 = sequ[st.top()].sum1;

	sumT2 = sequ[st.top()].sum2;

	sumT = sequ[st.top()].sum;

	nr = sequ[st.top()].right;

	nl = sequ[st.top()].left;

	st.pop();

	while (!st.empty())

	{

		int now = st.top();

		st.pop();

		if (sequ[now].left == nr)

		{

			sumT0 = max(sumT0, max(sequ[now].sum0, max(sequ[now].sum1, max(sumT2, sumT2 + sequ[now].sum1))));

			sumT1 = max(sumT1, sumT + sequ[now].sum1);

			sumT2 = max(sequ[now].sum2, sequ[now].sum + sumT2);

			sumT = sumT + sequ[now].sum;

			nr = sequ[now].right;

		}

		else

		{

			sumT0 = max(sumT0, max(sequ[now].sum0, max(sequ[now].sum2, max(sumT1, sumT1 + sequ[now].sum2))));

			sumT1 = max(sequ[now].sum1, sequ[now].sum + sumT1);

			sumT2 = max(sumT2, sumT + sequ[now].sum2);

			sumT = sumT + sequ[now].sum;

			nl = sequ[now].left;

		}

	}

	return sumT0;

}

int main()

{

	int n, m;

	scanf("%d%d", &n, &m);

	build(1, 1, n);

	for (int i = 0; i < n; i++)

	{

		int a;

		scanf("%d", &a);

		update(1, i + 1, a);

	}

	for (int i = 0; i < m; i++)

	{

		while (!st.empty())

			st.pop();

		bool p;

		scanf("%d", &p);

		if (p)

		{

			int x, w;

			scanf("%d%d", &x, &w);

			update(1, x, w);

		}

		else

		{

			int l, r;

			scanf("%d%d", &l, &r);

			ask(l, r, 1);

			printf("%d\n", answer());

		}

	}

	return 0;

}