resftlmuttmotw @ 2019-08-09 10:54:55
题目
只有第一个点对了
#include <cmath>
#include <cstdio>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
#define isdigit(x) ('1' <= (x)&&(x) <= '9')
template<typename T>
inline T Read(T Type)
{
T x = 0;
bool f = 0;
char a = getchar();
while(!isdigit(a)) {if(a == '-') f = 1;a = getchar();}
while(isdigit(a)) x = (x << 1) + (x << 3) + a - '0',a = getchar();
if(f) x *= -1;
return x;
}
const int MAXN = 500005;
int Left,Right,a[MAXN];
struct Node
{
int maxl,L_max,R_max,Mid_max,sum;
}Tree[MAXN << 2];
inline void Tree_build(int l,int r,int k)
{
if(l == r)
{
Tree[k].sum = Tree[k].maxl = Tree[k].L_max = Tree[k].Mid_max = Tree[k].R_max = a[l];
return;
}
int mid = l + r >> 1,k1 = k << 1;
int k2 = k1 ^ 1;
Tree_build(l,mid,k1);
Tree_build(mid + 1,r,k2);
Tree[k].sum = Tree[k1].sum + Tree[k2].sum;
Tree[k].maxl = max(Tree[k1].maxl,Tree[k2].maxl);
Tree[k].L_max = max(Tree[k1].L_max,Tree[k1].sum + Tree[k2].L_max);
Tree[k].R_max = max(Tree[k2].R_max,Tree[k2].sum + Tree[k1].R_max);
Tree[k].Mid_max = Tree[k1].R_max + Tree[k2].L_max;
Tree[k].maxl = max(Tree[k].maxl,Tree[k].Mid_max);
//printf("%d %d %d %d %d\n",l,r,Tree[k].maxl,Tree[k].L_max,Tree[k].R_max);
}
inline void modify(int l,int r,int k,int p,int s)
{
if(l == r)
{
Tree[k].sum = Tree[k].maxl = Tree[k].L_max = Tree[k].Mid_max = Tree[k].R_max = s;
return;
}
int mid = l + r >> 1,k1 = k << 1;
int k2 = k1 ^ 1;
if(p <= mid) modify(l,mid,k1,p,s);
else modify(mid + 1,r,k2,p,s);
Tree[k].sum = Tree[k1].sum + Tree[k2].sum;
Tree[k].maxl = max(Tree[k1].maxl,Tree[k2].maxl);
Tree[k].L_max = max(Tree[k1].L_max,Tree[k1].sum + Tree[k2].L_max);
Tree[k].R_max = max(Tree[k2].R_max,Tree[k2].sum + Tree[k1].R_max);
Tree[k].Mid_max = Tree[k1].R_max + Tree[k2].L_max;
Tree[k].maxl = max(Tree[k].maxl,Tree[k].Mid_max);
//printf("%d %d %d\n",l,r,Tree[k].maxl);
}
inline Node query(int l,int r,int k)
{
if(Left <= l&&r <= Right) return Tree[k];
int mid = l + r >> 1;
if(Right <= mid) return query(l,mid,k << 1);
else if(mid < Left) return query(mid + 1,r,k << 1 ^ 1);
else {
Node New,a1 = query(l,mid,k << 1),a2 = query(mid + 1,r,k << 1 ^ 1);
New.maxl = max(a1.maxl,a2.maxl);
New.Mid_max = a1.R_max + a2.L_max;
New.maxl = max(New.maxl,New.Mid_max);
New.L_max = max(a1.L_max,a1.sum + a2.L_max);
New.R_max = max(a2.R_max,a2.sum + a1.R_max);
New.sum = a1.sum + a2.sum;
return New;
}
}
int main()
{
int i,n = Read(1),m = Read(1);
for(i = 1;i <= n;i++) a[i] = Read(1);
Tree_build(1,n,1);
while(m--)
{
int k = Read(1);
Left = Read(1),Right = Read(1);
if(k == 1)
{
if(Left > Right) swap(Left,Right);
Node Ans = query(1,n,1);
printf("%d\n",Ans.maxl);
} else modify(1,n,1,Left,Right);
}
return 0;
}
by lx_zjk @ 2019-08-20 21:32:54
query有问题啊
by resftlmuttmotw @ 2019-08-21 18:34:15
@Hock
其实是读入优化写错了