`ask` 里面 `if(l<=t[now].l&&t[now].r<=r)`。
by LiJoQiao @ 2024-02-27 22:02:19
```cpp
ans.lma=max(a.sum+b.lma,ans.ma);
ans.rma=max(b.sum+a.rma,ans.ma);
```
by LiJoQiao @ 2024-02-27 22:03:59
有没有可能是
```cpp
ans.lma=max(a.sum+b.lma,a.lma);
ans.rma=max(b.sum+a.rma,b.rma);
```
by chroneZ @ 2024-02-27 22:05:32
提供马蜂不好看,思路不清晰的线段树
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+1;
int a[N];
int qzh[N];
int b[N];
struct Tree
{
#define lson(x) x<<1
#define rson(x) x<<1|1
struct node
{
int l,r,val,lz;
int lmax,rmax;
int max;
}tree[N<<2];
void pushup(int x)
{
tree[x].val = tree[lson(x)].val + tree[rson(x)].val;
tree[x].lmax = max(tree[lson(x)].lmax,tree[lson(x)].val + tree[rson(x)].lmax);
tree[x].rmax = max(tree[rson(x)].rmax,tree[rson(x)].val + tree[lson(x)].rmax);
tree[x].max = max(max(tree[lson(x)].max,tree[rson(x)].max),tree[lson(x)].rmax+tree[rson(x)].lmax);
return;
}
void build(int l,int r,int x)
{
tree[x].l = l;
tree[x].r = r;
if(l == r)
{
tree[x].val = a[l];
tree[x].lmax = a[l];
tree[x].rmax = a[l];
tree[x].max = a[l];
return;
}
int mid = l+r>>1;
build(l,mid,lson(x));
build(mid+1,r,rson(x));
pushup(x);
}
void pushdown(int x)
{
if(tree[x].lz)
{
tree[lson(x)].lz += tree[x].lz;
tree[rson(x)].lz += tree[x].lz;
int mid = tree[x].l + tree[x].r >> 1;
tree[lson(x)].val += tree[x].lz * (mid-tree[x].l+1);
tree[rson(x)].val += tree[x].lz * (tree[x].r-mid);
tree[x].lz &= 0;
}
}
void update(int l,int r,int k,int x)
{
if(tree[x].l == l&&tree[x].r == r)
{
tree[x].max = tree[x].lmax = tree[x].rmax = tree[x].val = k;
return;
}
pushdown(x);
int mid = tree[x].l + tree[x].r >> 1;
if(l>mid) update(l,r,k,rson(x));
else update(l,r,k,lson(x));
pushup(x);
}
int query(int l,int r,int x)
{
if(l<=tree[x].l && tree[x].r <= r)
{
return tree[x].val;
}
pushdown(x);
int mid = tree[x].l + tree[x].r >> 1;
int ans{};
if(l<=mid) ans+=query(l,r,lson(x));
if(r>mid) ans+=query(l,r,rson(x));
return ans;
}
node query2(int l,int r,int x)
{
if(l<=tree[x].l && tree[x].r <= r)
{
return tree[x];
}
pushdown(x);
int mid = tree[x].l + tree[x].r >> 1;
if(mid<l)return query2(l,r,rson(x));
else if(mid>=r) return query2(l,r,lson(x));
else
{
node a,b;
a = query2(l,r,lson(x));
b = query2(l,r,rson(x));
node t;
t.max = max(max(a.max,b.max),a.rmax+b.lmax);
t.lmax = max(a.lmax,a.val+b.lmax);
t.rmax = max(b.rmax,a.rmax+b.val);
return t;
}
}
}tree[2];
signed main()
{
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n,m;
cin>>n>>m;
for(int i{1};i<=n;i++)
{
cin>>a[i];
}
tree[1].build(1,n,1);
while(m--)
{
int k;
cin>>k;
int l,r;
cin>>l>>r;
if(k == 1)
{
if(l>r) swap(l,r);
cout<<tree[1].query2(l,r,1).max<<endl;
}
else
{
tree[1].update(l,l,r,1);
}
}
}//13
//1 2 1 1 2 1 0
```
by wangmingwei @ 2024-02-28 14:34:01