放错了，这个是dalao写的
by ___I_AK_IOI @ 2018-10-03 18:18:50
本蒟蒻的代码
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<deque>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
const int MAXN = 1e6 + 7;
struct node
{
int lmax,rmax,maxn,nnum,left,right;
node *leftchild,*rightchild;
}*TREE,Tree[MAXN];
int A[MAXN],n,top,ans;
void update(node* &tree)
{
tree->nnum = tree->leftchild->nnum + tree->rightchild->nnum;
tree->lmax = max(tree->leftchild->lmax,tree->leftchild->nnum + tree->rightchild->lmax);
tree->rmax = max(tree->rightchild->rmax,tree->rightchild->nnum + tree->leftchild->rmax);
tree->maxn = max(max(tree->leftchild->maxn,tree->rightchild->maxn),tree->lmax + tree->rmax);
}
void build(node* &tree,int l,int r)
{
tree = &Tree[++top];
if(l == r)
{
tree->left = l;
tree->right = r;
tree->lmax = A[l];
tree->rmax = A[l];
tree->nnum = A[l];
tree->maxn = A[l];
return;
}
int mid = (l + r) >> 1;
build(tree->leftchild,l,mid);
build(tree->rightchild,mid+1,r);
update(tree);
}
*node query(node *tree,int l,int r)
{
if(l <= tree->left && tree->right <= r)
return tree;
int mid = (tree->left + tree->right) >> 1;
if(l <= mid)return query(tree->leftchild,l,mid);
if(r > mid)return query(tree->rightchild,mid+1,r);
node *ll,*rr,*thebest;
ll = query(tree->leftchild,l,mid);
rr = query(tree->rightchild,mid+1,r);
thebest->nnum = ll->nnum + rr->nnum;
thebest->lmax = max(ll->lmax,ll->nnum + rr->lmax);
thebest->rmax = max(rr->rmax,rr->nnum + ll->rmax);
thebest->maxn = max((ll->maxn))
return thebest;
}
int main()
{
int i,m;
cin >> n;
for(i = 1;i <= n; i++)
cin >> A[i];
build(TREE,1,n);
cin >> m;
int a,b;
while(m--)
{
ans = 0;
cin >> a >> b;
cout << query(TREE,a,b) << endl;
}
return 0;
}
```
by ___I_AK_IOI @ 2018-10-03 18:19:22
f**k tree很强
by 林则徐左宗棠 @ 2018-10-03 18:23:24
怪物……
by Ticzone @ 2018-10-03 18:24:20
@[黑水玄蛇真棒](/space/show?uid=116774) 那是dalao的代码放错了，dalao说让我看着改，结果发现不是凉凉
by ___I_AK_IOI @ 2018-10-03 18:29:56
@[白哥小葱](/space/show?uid=54520)
好吧我作为蒟蒻一点都看不懂
by 林则徐左宗棠 @ 2018-10-03 18:31:45
ORz
by Viston @ 2018-10-03 18:44:33
@[白哥小葱](/space/show?uid=54520)
话说直接把状态写个结构体多好
```cpp
struct p{
int l,r,sum,s;
p(int l=0,int r=0,int sum=0,int s=0):l(l),r(r),sum(sum),s(s){}
friend p operator + (const p &a,const p &b){
return p(max(a.l,a.s+b.l),max(b.r,a.r+b.s),max(max(a.sum,b.sum),a.r+b.l),a.s+b.s);
}
p &operator = (int x){s=l=r=sum=x;return *this;}
};
```
by kraylas @ 2018-10-03 19:22:14
@[花_Q](/space/show?uid=87940) 就是因为不习惯才写的指针
by ___I_AK_IOI @ 2018-10-03 19:49:17
@[白哥小葱](/space/show?uid=54520) 那就用指针的线段树套这个结构体啊qwq
~~不要吐槽我丑陋的代码~~
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 5e5+5;
int mian(){
int s=0,f=1;char ch;
while(!isdigit(ch=getchar()))(ch=='-')&&(f=-1);
for(s=ch-'0';isdigit(ch=getchar());s=s*10+ch-'0');
return s*f;
}
/*
子供の时の梦は言えますか
その梦すら 沟に 舍てたのは
*/
struct p{
int l,r,sum,s;
p(int l=0,int r=0,int sum=0,int s=0):l(l),r(r),sum(sum),s(s){}
friend p operator + (const p &a,const p &b){
return p(max(a.l,a.s+b.l),max(b.r,a.r+b.s),max(max(a.sum,b.sum),a.r+b.l),a.s+b.s);
}
p &operator = (int x){s=l=r=sum=x;return *this;}
};
struct Seq{
int l,r;
p s;
Seq *ch[2];
void up(){s=ch[0]->s+ch[1]->s;}
int mid(){return l+r>>1;}
};
typedef Seq* ptr;
ptr root;
int n,m;
void build(int l,int r,ptr &o=root){
o=new Seq;o->l=l,o->r=r;
if(l==r){
o->s=mian();
return;
}
int mid=o->mid();
build(l,mid,o->ch[0]);
build(mid+1,r,o->ch[1]);
o->up();
}
void change(int pos,int v,ptr o=root){
if(o->l==o->r){o->s=v;return;}
int mid=o->mid();
if(pos<=mid)change(pos,v,o->ch[0]);
else change(pos,v,o->ch[1]);
o->up();
}
p getsum(int l,int r,ptr o=root){
if(l<=o->l&&o->r<=r){return o->s;}
int mid=o->mid();
if(r<=mid)return getsum(l,r,o->ch[0]);
if(l>mid)return getsum(l,r,o->ch[1]);
return getsum(l,r,o->ch[0])+getsum(l,r,o->ch[1]);
}
int main(){
// freopen("data.in","r",stdin);
// freopen("fuck.out","w",stdout);
n=mian(),m=mian();
build(1,n,root);
while(m--){
int op=mian(),x=mian(),y=mian();
if(op==1)((x>y)&&(x^=y^=x^=y)),printf("%d\n",getsum(x,y).sum);
if(op==2)change(x,y);
}
return 0;
}
```
by kraylas @ 2018-10-03 19:58:02