4301 Can you answer on these queries III 0x40「数据结构进阶」例题
描述
给定长度为N的数列A，以及M条指令 (N≤500000, M≤100000)，每条指令可能是以下两种之一：
“2 x y”，把 A[x] 改成 y。
“1 x y”，查询区间 [x,y] 中的最大连续子段和，即 max(x≤l≤r≤y)? { ∑(i=l~r) A[i] }。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数N,M
第二行N个整数Ai
接下来M行每行3个整数k,x,y，k=1表示查询（此时如果x>y，请交换x,y），k=2表示修改
输出格式
对于每个询问输出一个整数表示答案。
样例输入
5 3 1 2 -3 4 5 1 2 3 2 2 -1 1 3 2
样例输出
2 -1
数据范围与约定
- 对于100%的数据: N≤500000, M≤100000, |Ai|<=1000
线段树板子啊。线段树代码风格要改~ 结构体有他的好处。。。。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define oo cout<<"!!!"<<endl;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
//headconst int maxn = 2e6+1111;struct node
{int l,r,dat,sum,dl,dr;
}t[maxn];
int a[maxn];void pushup(int i)
{t[i].sum = t[i<<1].sum + t[i<<1|1].sum;t[i].dl = max(t[i<<1].dl,t[i<<1].sum + t[i<<1|1].dl);t[i].dr = max(t[i<<1|1].dr,t[i<<1|1].sum + t[i<<1].dr);t[i].dat = max(t[i<<1].dat,t[i<<1|1].dat);t[i].dat = max(t[i].dat,t[i<<1].dr + t[i<<1|1].dl);
}
void build(int i,int l,int r)
{t[i].l = l;t[i].r = r;if(l == r){int x;scanf("%d",&x);t[i].sum = t[i].dat = t[i].dl = t[i].dr = x;return;} int mid = (l+r)>>1;build(i<<1,l,mid);build(i<<1|1,mid+1,r);pushup(i);
}void update(int x,int v,int i)
{if(t[i].l == t[i].r){t[i].sum = t[i].dat = t[i].dl = t[i].dr = v;return;}int mid = (t[i].l + t[i].r)>>1;if(x <= mid)update(x,v,i<<1);else update(x,v,i<<1|1);pushup(i);
}node query(int ql,int qr,int i)
{if(ql <= t[i].l && qr >= t[i].r)return t[i];int mid = (t[i].l + t[i].r)>>1;if(qr <= mid)return query(ql,qr,i<<1);if(ql > mid)return query(ql,qr,i<<1|1);node a = query(ql,qr,i<<1);node b = query(ql,qr,i<<1|1);node c;c.sum = a.sum + b.sum;c.dl = max(a.dl,a.sum + b.dl);c.dr = max(b.dr,b.sum + a.dr);c.dat = max(max(a.dat,b.dat),a.dr + b.dl);return c;
}int main()
{int n,q;cin>>n>>q;build(1,1,n);rep(i,1,q+1){int k,x,y;scanf("%d%d%d",&k,&x,&y);if(k == 2)update(x,y,1);else {if(y<x)swap(x,y);printf("%d\n",query(x,y,1).dat);}}return 0;
}