mxr已死 @ 2019-08-08 20:00:11
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<vector>
#define maxn 500005
#define rint register int
#define ll long long
#define inf 0x3f3f3f3f
#define pb push_back
#define mod (int)1e9 + 7
using namespace std;
inline int read()
{
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}
struct SegmentTree
{
int l, r, sum, lmax, rmax, dat;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define lm(x) tree[x].lmax
#define rm(x) tree[x].rmax
#define sum(x) tree[x].sum
#define dat(x) tree[x].dat
} tree[maxn*4];
int a[maxn], n, m;
inline void update (int p)
{
cout<<"update"<<endl;
sum(p) = sum(p*2) + sum(p*2+1);
lm(p) = max(lm(p*2), sum(p*2) + lm(p*2+1));
rm(p) = max(rm(p*2+1), sum(p*2+1) + rm(p*2));
dat(p) = max(dat(p*2), max(dat(p*2+1), lm(p*2+1) + rm(p*2)));
}
inline void build (int p, int l, int r)
{
cout<<"build"<<endl;
l(p)=l, r(p)=r;
if (l==r) { lm(p) = rm(m) = sum(p) = dat(p) = a[l]; return; }
int mid = (l(p)+r(p)) >> 1;
build (p*2, l, mid);
build (p*2+1, mid+1, r);
update(p);
}
void change (int p, int pos, int d)
{
cout<<"change"<<endl;
if (l(p) == r(p))
{
lm(p) = r(m) = sum(p) = dat(p) = d;
return;
}
int mid = (l(p)+r(p)) >> 1;
if (pos <= mid) change(p*2, pos, d);
else change(p*2+1, pos, d);
update(p);
}
SegmentTree query (int p, int l, int r)
{
cout<<"query"<<endl;
if (l<=l(p) && r>=r(p)) return tree[p];
int mid = (l(p)+r(p)) >> 1;
if (r <= mid) return query(p*2, l, r);
else if (l > mid) return query(p*2+1, l, r);
else
{
SegmentTree x=query(p*2, l, r), y=query(p*2+1, l, r), res;
res.sum = x.sum + y.sum;
res.lmax = max(x.sum + y.lmax, x.lmax);
res.rmax = max(y.sum + x.rmax, y.rmax);
res.dat = max( max(x.dat, y.dat), x.rmax + y.lmax);
return res;
}
}
int main()
{
n=read(), m=read();
for (rint i=1; i<=n; ++i) a[i]=read();
build (1, 1, n);
while (m--)
{
int op = read();
int x=read(), y=read();
if (op == 1)
{
cout<<"op1"<<endl;
if (x > y) swap(x, y);
SegmentTree ans = query(1, x, y);
write(ans.dat), puts("");
}
else if (op == 2) change(1, x, y),cout<<"op2"<<endl;
}
return 0;
}
by FlowNews @ 2019-08-08 20:18:12
万能头文件了解一下
by ud2_ @ 2019-08-08 20:18:23
cout<<"change"<<endl;
if (l(p) == r(p))
{
- lm(p) = r(m) = sum(p) = dat(p) = d;
+ lm(p) = rm(p) = sum(p) = dat(p) = d;
return;
}
int mid = (l(p)+r(p)) >> 1;
by mxr已死 @ 2019-08-08 20:33:30
@sjx233 太谢谢啦