chlchl @ 2022-11-06 16:24:40
有交换
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
const int M = N << 2;
int n, m, a[N];
int ans[M], lm[M], rm[M], sum[M];
struct node{
int res, lres, rres, sum;
};
#define ls(o) (o << 1)
#define rs(o) (o << 1 | 1)
void pushup(int o){
sum[o] = sum[ls(o)] + sum[rs(o)];
lm[o] = max(lm[ls(o)], sum[ls(o)] + lm[rs(o)]);
rm[o] = max(rm[rs(o)], sum[rs(o)] + rm[ls(o)]);
ans[o] = max(max(ans[ls(o)], ans[rs(o)]), rm[ls(o)] + lm[rs(o)]);
}
void build(int o, int l, int r){
if(l == r){
ans[o] = lm[o] = rm[o] = sum[o] = a[l];
return ;
}
int mid = (l + r) >> 1;
build(ls(o), l, mid);
build(rs(o), mid + 1, r);
pushup(o);
}
void update(int o, int l, int r, int p, int v){
if(l == r){
ans[o] = lm[o] = rm[o] = sum[o] = v;
return ;
}
int mid = (l + r) >> 1;
if(p <= mid)
update(ls(o), l, mid, p, v);
else
update(rs(o), mid + 1, r, p, v);
pushup(o);
}
node query(int o, int l, int r, int s, int t){
if(l == r)
return (node){ans[o], lm[o], rm[o], sum[o]};
int mid = (l + r) >> 1;
node now = (node){0, 0, 0, 0};
if(t <= mid)
return query(ls(o), l, mid, s, t);
if(s > mid)
return query(rs(o), mid + 1, r, s, t);
node p = query(ls(o), l, mid, s, t);
node q = query(rs(o), mid + 1, r, s, t);
now.sum = p.sum + q.sum;
now.lres = max(p.lres, p.sum + q.lres);
now.rres = max(q.rres, q.sum + p.rres);
now.res = max(max(p.res, q.res), p.rres + q.lres);
return now;
}
int main(){
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++)
scanf("%d", &a[i]);
build(1, 1, n);
while(m--){
int op, a, b;
scanf("%d%d%d", &op, &a, &b);
if(op == 1)
printf("%d\n", query(1, 1, n, min(a, b), max(a, b)).res);
else
update(1, 1, n, a, b);
}
return 0;
}by wukaichen888 @ 2022-11-06 16:26:12
@caihaolang
测试数据可能会出现 a > b 的情况，需要进行交换；
by chlchl @ 2022-11-06 16:26:43
@wukaichen888 交换了啊。
by wukaichen888 @ 2022-11-06 16:26:49
@caihaolang 我犯过一样的错，会栈溢出 MLE
by wukaichen888 @ 2022-11-06 16:27:30
@caihaolang 抱歉，看错了
by chlchl @ 2022-11-06 16:28:00
@wukaichen888 我这是 TLE 啊，而且换了
by chlchl @ 2022-11-06 16:29:03
@wukaichen888 wssb，
by bamboo12345 @ 2022-11-06 16:29:37
@caihaolang update有没有交换?
by chlchl @ 2022-11-06 16:29:39
线段树太久没写了，手生了。此贴完结。
by chlchl @ 2022-11-06 16:29:54
@bamboo123 query 写成单点了。
by wukaichen888 @ 2022-11-06 16:34:02
放一下我的远古代码吧，感觉比较易懂
#include<bits/stdc++.h>
//#include<type_traits>
//#include<debug/debug.h>
//#include<bits/stl_pair.h>
//#pragma GCC optimize(1)
//#pragma GCC optimize(2)
//#ifndef _STL_ALGOBASE_H
//#if __cplusplus > 201703L
//#define _STL_ALGOBASE_H 1
//#if __cplusplus >= 201103L
//#include<bits/c++config.h>
//#include<ext/type_traits.h>
//#include<bits/functexcept.h>
//#include<bits/stl_iterator.h>
//#include<ext/numeric_traits.h>
//#include<bits/concept_check.h>
//#include<bits/predefined_ops.h>
//#include<bits/cpp_type_traits.h>
//#include<bits/move.h> // For std::swap
//#include<bits/stl_iterator_base_types.h>
//#include<bits/stl_iterator_base_funcs.h>
using namespace std;
//#define int long long
//#define ll long long int
#define ull unsigned long long
typedef long long ll;
//#define I using
//#define AK namespace
//#define IOI std
//I AK IOI;
int n,m,a[500005];
struct point
{
int lmax,rmax,maxx,sum;
}
tree[2000005];
point add(point a,point b)
{
point c;
c.sum=a.sum+b.sum;
c.lmax=max(a.lmax,a.sum+b.lmax);
c.rmax=max(a.rmax+b.sum,b.rmax);
c.maxx=max(a.rmax+b.lmax,max(a.maxx,b.maxx));
return c;
}
void pre(int k,int l,int r)
{
if(l==r)
{
tree[k].lmax=tree[k].rmax=tree[k].maxx=tree[k].sum=a[l];
return ;
}
int mid=(l+r)>>1;
pre(k<<1,l,mid);
pre(k<<1|1,mid+1,r);
tree[k]=add(tree[k<<1],tree[k<<1|1]);
}
void change(int k,int l,int r,int x,int d)
{
if(l==r)
{
tree[k].lmax=tree[k].rmax=tree[k].maxx=tree[k].sum=d;
return ;
}
int mid=(l+r)>>1;
if(x<=mid)
change(k<<1,l,mid,x,d);
else
change(k<<1|1,mid+1,r,x,d);
tree[k]=add(tree[k<<1],tree[k<<1|1]);
return ;
}
point ask(int k,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
return tree[k];
int mid=(l+r)>>1;
if(y<=mid)
return ask(k<<1,l,mid,x,y);
if(mid<x)
return ask(k<<1|1,mid+1,r,x,y);
return add(ask(k<<1,l,mid,x,y),ask(k<<1|1,mid+1,r,x,y));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
pre(1,1,n);
for(int i=1,op,x,y;i<=m;i++)
{
scanf("%d%d%d",&op,&x,&y);
if(op==1)
{
if(x>y)
swap(x,y);
printf("%d\n",ask(1,1,n,x,y).maxx);
}
else
change(1,1,n,x,y);
}
}