mxr已死 @ 2019-08-08 21:50:01
#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) = rm(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 change(1, x, y);
}
return 0;
}
by By_Ha @ 2019-08-08 22:02:00
对拍: https://www.luogu.org/paste/14th2rvd
把对拍2的 print(r.randint(1,222222),end=' ')
改成 print(r.randint(-222222,222222),end=' ')
by IC_QQQ @ 2019-08-08 22:06:10
query()中,res可能需要初始化。
不对别打我。
@mxrmxr ,
by mxr已死 @ 2019-08-08 22:06:36
@By_Ha dalao您的对拍写的是伪程序吗?
by mxr已死 @ 2019-08-08 22:07:01
@IC_QQQ 好的,我试试
by mxr已死 @ 2019-08-08 22:07:28
@IC_QQQ 不是
by 星尘_星辰 @ 2019-08-08 22:15:00
@mxrmxr
情头?
by By_Ha @ 2019-08-08 22:48:07
@mxrmxr python, 你的程序命名std.exe,标答命名ans.exe,运行对拍1(会调用对拍2)