9pts->100pts
- 板块P4513 小白逛公园
- 楼主xiaoyuhao0503
- 当前回复1
- 已保存回复1
- 发布时间2024/4/9 21:40
- 上次更新2024/4/10 10:55:35
查看原帖
被骇客银狼阻止的越权访问保存失败
9pts->100pts
应该没有人会错，但我还是发一下。
9pts:
#include<bits/stdc++.h>
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
using namespace std;
namespace FAST_IO{
char buf[1048576],*p1,*p2,ch;
int x,f;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1048576,stdin),p1==p2)?EOF:*p1++)
inline int read(){
x=f=0,ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=1;
ch=getchar();
}
do x=(x<<1)+(x<<3)+(ch^48),ch=getchar();while(isdigit(ch));
return f?-x:x;
}
inline void write(const int &p){
if(9<p)write(p/10);
putchar(p%10|48);
}
inline void writeln(const int &p){
if(p<0)putchar('-'),write(-p);else write(p);
putchar(10);
}
#undef getchar
}
using FAST_IO::read;
using FAST_IO::writeln;
struct NOTE{
int l,r,sum,maxn,maxl,maxr;
NOTE():l(0),r(0),sum(0),maxn(0),maxl(0),maxr(0){}
}tree[2000005];
int n,m;
inline void push_up(NOTE &root,const NOTE &son1,const NOTE &son2){
if(son1.maxr<0&&son2.maxl<0)root.maxn=max(son1.maxr,son2.maxl);
else{
root.maxn=0;
if(son1.maxr>0)root.maxn+=son1.maxr;
if(son2.maxl>0)root.maxn+=son2.maxl;
}
root.maxn=max(root.maxn,son1.maxn);
root.maxn=max(root.maxn,son2.maxn);
root.maxl=max(son1.maxl,son1.maxn+son2.maxl);
root.maxr=max(son2.maxr,son2.maxn+son1.maxr);
root.sum=son1.sum+son2.sum;
}
void build(const int &p,const int &pl,const int &pr){
tree[p].l=pl,tree[p].r=pr;
if(pl==pr){tree[p].sum=tree[p].maxl=tree[p].maxr=tree[p].maxn=read();return;}
register int mid((pl+pr)>>1);
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
push_up(tree[p],tree[ls(p)],tree[rs(p)]);
}
void change(const int &wei,const int &p,const int &d){
if(tree[p].l==tree[p].r){tree[p].maxl=tree[p].maxn=tree[p].maxr=tree[p].sum=d;return;}
int mid((tree[p].l+tree[p].r)>>1);
if(wei<=mid)change(wei,ls(p),d);else change(wei,rs(p),d);
push_up(tree[p],tree[ls(p)],tree[rs(p)]);
}
NOTE answer(const int &L,const int &R,const int &p){
if(L<=tree[p].l&&tree[p].r<=R)return tree[p];
int mid((tree[p].l+tree[p].r)>>1);
if(L<=mid&&mid<R){
NOTE res;
push_up(res,answer(L,R,ls(p)),answer(L,R,rs(p)));
return res;
}else if(L<=mid)return answer(L,R,ls(p));
else return answer(L,R,rs(p));
}
int main(){
n=read(),m=read();
build(1,1,n);
while(m--){
if(read()==1){
register int a(read()),b(read());
if(a>b)swap(a,b);
writeln(answer(a,b,1).maxn);
}else{
register int a(read()),b(read());
change(a,1,b);
}
}
return 0;
}
#undef ls
#undef rs
/*
*
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/
100pts:
#include<bits/stdc++.h>
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
using namespace std;
namespace FAST_IO{
char buf[1048576],*p1,*p2,ch;
int x,f;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1048576,stdin),p1==p2)?EOF:*p1++)
inline int read(){
x=f=0,ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=1;
ch=getchar();
}
do x=(x<<1)+(x<<3)+(ch^48),ch=getchar();while(isdigit(ch));
return f?-x:x;
}
inline void write(const int &p){
if(9<p)write(p/10);
putchar(p%10|48);
}
inline void writeln(const int &p){
if(p<0)putchar('-'),write(-p);else write(p);
putchar(10);
}
#undef getchar
}
using FAST_IO::read;
using FAST_IO::writeln;
struct NOTE{
int l,r,sum,maxn,maxl,maxr;
NOTE():l(0),r(0),sum(0),maxn(0),maxl(0),maxr(0){}
}tree[2000005];
int n,m;
inline void push_up(NOTE &root,const NOTE &son1,const NOTE &son2){
if(son1.maxr<0&&son2.maxl<0)root.maxn=max(son1.maxr,son2.maxl);
else{
root.maxn=0;
if(son1.maxr>0)root.maxn+=son1.maxr;
if(son2.maxl>0)root.maxn+=son2.maxl;
}
root.maxn=max(root.maxn,son1.maxn);
root.maxn=max(root.maxn,son2.maxn);
root.maxl=max(son1.maxl,son1.sum+son2.maxl);
root.maxr=max(son2.maxr,son2.sum+son1.maxr);
root.sum=son1.sum+son2.sum;
}
void build(const int &p,const int &pl,const int &pr){
tree[p].l=pl,tree[p].r=pr;
if(pl==pr){tree[p].sum=tree[p].maxl=tree[p].maxr=tree[p].maxn=read();return;}
register int mid((pl+pr)>>1);
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
push_up(tree[p],tree[ls(p)],tree[rs(p)]);
}
void change(const int &wei,const int &p,const int &d){
if(tree[p].l==tree[p].r){tree[p].maxl=tree[p].maxn=tree[p].maxr=tree[p].sum=d;return;}
int mid((tree[p].l+tree[p].r)>>1);
if(wei<=mid)change(wei,ls(p),d);else change(wei,rs(p),d);
push_up(tree[p],tree[ls(p)],tree[rs(p)]);
}
NOTE answer(const int &L,const int &R,const int &p){
if(L<=tree[p].l&&tree[p].r<=R)return tree[p];
int mid((tree[p].l+tree[p].r)>>1);
if(L<=mid&&mid<R){
NOTE res;
push_up(res,answer(L,R,ls(p)),answer(L,R,rs(p)));
return res;
}else if(L<=mid)return answer(L,R,ls(p));
else return answer(L,R,rs(p));
}
int main(){
n=read(),m=read(),build(1,1,n);
while(m--){
register int k(read()),a(read()),b(read());
if(k==1){
if(a>b)swap(a,b);
writeln(answer(a,b,1).maxn);
}else change(a,1,b);
}
return 0;
}
#undef ls
#undef rs
/*
*
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/
一定要避坑！！！
不要像我一样，把
inline void push_up(NOTE &root,const NOTE &son1,const NOTE &son2){
if(son1.maxr<0&&son2.maxl<0)root.maxn=max(son1.maxr,son2.maxl);
else{
root.maxn=0;
if(son1.maxr>0)root.maxn+=son1.maxr;
if(son2.maxl>0)root.maxn+=son2.maxl;
}
root.maxn=max(root.maxn,son1.maxn);
root.maxn=max(root.maxn,son2.maxn);
root.maxl=max(son1.maxl,son1.sum+son2.maxl);
root.maxr=max(son2.maxr,son2.sum+son1.maxr);
root.sum=son1.sum+son2.sum;
}
写成
inline void push_up(NOTE &root,const NOTE &son1,const NOTE &son2){
if(son1.maxr<0&&son2.maxl<0)root.maxn=max(son1.maxr,son2.maxl);
else{
root.maxn=0;
if(son1.maxr>0)root.maxn+=son1.maxr;
if(son2.maxl>0)root.maxn+=son2.maxl;
}
root.maxn=max(root.maxn,son1.maxn);
root.maxn=max(root.maxn,son2.maxn);
root.maxl=max(son1.maxl,son1.maxn+son2.maxl);
root.maxr=max(son2.maxr,son2.maxn+son1.maxr);
root.sum=son1.sum+son2.sum;
}
加载中...