主要是 #define 看着很帅,就弄了个。
参考文献
算法进阶指南
C++ 代码
#include <iostream>
using namespace std;
const int N = 500010;
int w[N];
int n , m;
struct Tr
{
int l , r;
int lmax , rmax , tmax, sum;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define sum(x) tr[x].sum
#define lmax(x) tr[x].lmax
#define rmax(x) tr[x].rmax
#define tmax(x) tr[x].tmax
}tr[N * 4];
void pushup(Tr &u , Tr &l , Tr &r)
{
u.sum = l.sum + r.sum;
u.lmax = max(l.lmax , l.sum + r.lmax);
u.rmax = max(r.rmax , r.sum + l.rmax);
u.tmax = max(max(l.tmax , r.tmax) , l.rmax + r.lmax);
}
void pushup(int u)
{
pushup(tr[u] , tr[u << 1] , tr[u << 1 | 1]);
}
void build(int u , int l , int r)
{
if(l == r)
{
tr[u] = {l , r , w[r] , w[r] , w[r] , w[r]};
return ;
}
else
{
tr[u] = {l , r};
int mid = l + r >> 1;
build(u << 1 , l , mid) , build(u << 1 | 1 , mid + 1 , r);
pushup(u);
}
}
void modify(int u , int x , int v)
{
if(l(u) == x && r(u) == x) tr[u] = {x , x , v , v , v , v};
else
{
int mid = l(u) + r(u) >> 1;
if(x <= mid) modify(u << 1 , x , v);
else modify(u << 1 | 1 , x , v);
pushup(u);
}
}
Tr query(int u , int l , int r)
{
if(l(u) >= l && r(u) <= r) return tr[u];
else
{
int mid = l(u) + r(u) >> 1;
if(r <= mid) return query(u << 1 , l , r);
else if(l > mid) return query(u << 1 | 1 , l , r);
else
{
auto left = query(u << 1 , l , r);
auto right = query(u << 1 | 1 , l , r);
Tr res;
pushup(res , left , right);
return res;
}
}
}
int main()
{
scanf("%d%d" , &n , &m);
for(int i = 1;i <= n;i ++) scanf("%d" , &w[i]);
build(1 , 1 , n);
// cout << n << " " << m << endl;
while(m --)
{
int op;
scanf("%d" , &op);
if(op == 1)
{
int x , y;
scanf("%d%d",&x, &y);
if(x > y) swap(x , y);
auto res = query(1 , x , y);
printf("%d\n" , res.tmax);
}
else
{
int x , y;
scanf("%d%d",&x, &y);
modify(1 , x , y);
}
}
return 0;
}