给定长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“1 x y”，查询区间 [x,y] 中的最大连续子段和，即 maxx≤l≤r≤ymaxx≤l≤r≤y{∑ri=lA[i]∑i=lrA[i]}。
2、“2 x y”，把 A[x] 改成 y。
对于每个查询指令，输出一个整数表示答案。
输入格式
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行每行3个整数k,x,y，k=1表示查询（此时如果x>y，请交换x,y），k=2表示修改。
输出格式
对于每个查询指令输出一个整数表示答案。
每个答案占一行。
数据范围
N≤500000,M≤100000N≤500000,M≤100000
输入样例：
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2
输出样例：
2
-1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eps 1e-9
const int inf =
0x3f3f3f3f;
const int mod = 1e9+
7;
const int maxn =
500000 +
8;
int n, m, k, x, y;
ll a[maxn];
struct node
{
int l, r;
ll sum, dat, lmax, rmax;
}tree[4 *
maxn];
void push_down(
int i)
{
tree[i].sum = tree[i *
2].sum + tree[i *
2 +
1].sum;
tree[i].lmax = max(tree[i *
2].lmax, tree[i *
2].sum + tree[i *
2 +
1].lmax);
///紧靠左端的最大连续子段和
tree[i].rmax = max(tree[i *
2 +
1].rmax, tree[i *
2 +
1].sum + tree[i *
2].rmax);
///紧靠右端的最大连续子段和
tree[i].dat = max(tree[i *
2].dat, max(tree[i *
2 +
1].dat, tree[i *
2].rmax + tree[i *
2 +
1].lmax));
///区间连续最大字段和
}
void build(
int i,
int l,
int r)
{
tree[i].l =
l;
tree[i].r =
r;
if(l ==
r)
{
tree[i].sum =
a[l];
tree[i].dat =
a[l];
tree[i].lmax =
a[l];
tree[i].rmax =
a[l];
return;
}
int mid = (l + r) /
2;
build(i *
2, l, mid);
build(i *
2 +
1, mid +
1, r);
push_down(i);
}
void change(
int i,
int pos,
int k)
{
if(tree[i].l ==
tree[i].r)
{
tree[i].sum =
k;
tree[i].sum =
k;
tree[i].dat =
k;
tree[i].lmax =
k;
tree[i].rmax =
k;
return;
}
int mid = (tree[i].l + tree[i].r) /
2;
if(pos <=
mid)
change(i *
2, pos, k);
else
change(i *
2 +
1, pos, k);
push_down(i);
}
node tmp;
node search(int i,
int l,
int r)
{
if(tree[i].l >= l && tree[i].r <=
r)
{
return tree[i];
}
node a, b, c;
a.dat = a.lmax = a.rmax = a.sum = -inf;
///左儿子
b.dat = b.lmax = b.rmax = b.sum = -inf;
///右儿子
c.dat = c.lmax = c.rmax = -inf;
///父节点
c.sum =
0;
int mid = (tree[i].l + tree[i].r) /
2;
if(l <= mid && r <=
mid)
{
a = search(i *
2, l, r);
c.sum +=
a.sum;
}
else if(mid < r && mid <
l)
{
b = search(i *
2 +
1, l, r);
c.sum +=
b.sum;
}
else
{
a = search(i *
2, l, r);
b = search(i *
2 +
1, l, r);
c.sum += a.sum +
b.sum;
}
c.dat = max(c.dat, max(a.rmax + b.lmax, max(a.dat, b.dat)));
///区间连续最大字段和
c.lmax = max(c.lmax, max(a.lmax, a.sum + b.lmax));
///紧靠左端的最大连续子段和
c.rmax = max(c.rmax, max(b.rmax, b.sum + a.rmax));
///紧靠右端的最大连续子段和
return c;
}
int main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>
m;
for(
int i =
1; i <= n; i++
)
cin>>
a[i];
build(1,
1, n);
for(
int i =
0; i < m; i++
)
{
cin>>k>>x>>
y;
if(k ==
1)
{
if(x >
y)
swap(x, y);
cout<<search(
1, x, y).dat<<
'\n';
}
else if(k ==
2)
{
a[x] =
y;
change(1, x, y);
}
}
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/11432182.html
相关资源：JAVA上百实例源码以及开源项目
