cx2021ghj @ 2024-10-23 07:58:37
#include<bits/stdc++.h>
using namespace std;
struct ghj{
int l,r;
long long ans,ansl,ansr,cnt;
}tree[2000009];
int n,m,a[500009],op,x,l,r,d;
void push_up(int q){
tree[q].cnt=tree[q*2].cnt+tree[q*2+1].cnt;
tree[q].ansl=max(tree[q*2].ansl,tree[q*2].cnt+tree[q*2+1].ansl);
tree[q].ansr=max(tree[q*2+1].ansr,tree[q*2+1].cnt+tree[q*2].ansr);
tree[q].ans=max(max(tree[q*2].ans,tree[q*2+1].ans),tree[q*2].ansr+tree[q*2+1].ansl);
}
void build(int l,int r,int p=1){
tree[p].l=l;
tree[p].r=r;
if(l==r){
cin>>tree[p].cnt;
tree[p].ansl=tree[p].ansr=tree[p].ans=tree[p].cnt;
return;
}
int mid=(l+r)/2;
build(l,mid,p*2);
build(mid+1,r,p*2+1);
push_up(p);
}
void update(int x,int d,int p=1){
if(tree[p].l==tree[p].r){
tree[p].cnt=d;
tree[p].ansl=d;
tree[p].ansr=d;
tree[p].ans=d;
return;
}
int mid=(tree[p].l+tree[p].r)/2;
if(x<=mid) update(x,d,p*2);
else update(x,d,p*2+1);
push_up(p);
}
ghj query(int p,int l,int r){
if(l<=tree[p].l && tree[p].r<=r) return tree[p];
int mid=(tree[p].l+tree[p].r)/2;
if(r<=mid) return query(p*2,l,r);
else{
if(r>mid) return query(p*2+1,l,r);
else{
ghj t,a=query(p*2,l,r),b=query(p*2+1,l,r);
t.ansl=max(a.ansl,a.cnt+b.ansl);
t.ansr=max(b.ansr,a.ansr+b.cnt);
t.ans=max(max(a.ans,b.ans),a.ansr+b.ansl);
return t;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
build(1,n,1);
while(m--){
cin>>op;
if(op==1){
cin>>l>>r;
if(l>r)swap(l,r);
cout<<query(1,l,r).ans<<'\n';
}
else{
cin>>x>>d;
update(x,d);
}
}
}
by ShiYufan @ 2024-10-23 08:33:18
毋庸置疑线段树有问题
by HongLou_LaMiYa @ 2024-10-26 10:58:06
query写错了
#include<bits/stdc++.h>
using namespace std;
struct ghj{
int l,r;
long long ans,ansl,ansr,cnt;
}tree[2000009];
int n,m,a[500009],op,x,l,r,d;
void push_up(int q){
tree[q].cnt=tree[q*2].cnt+tree[q*2+1].cnt;
tree[q].ansl=max(tree[q*2].ansl,tree[q*2].cnt+tree[q*2+1].ansl);
tree[q].ansr=max(tree[q*2+1].ansr,tree[q*2+1].cnt+tree[q*2].ansr);
tree[q].ans=max(max(tree[q*2].ans,tree[q*2+1].ans),tree[q*2].ansr+tree[q*2+1].ansl);
}
void build(int l,int r,int p=1){
tree[p].l=l;
tree[p].r=r;
if(l==r){
cin>>tree[p].cnt;
tree[p].ansl=tree[p].ansr=tree[p].ans=tree[p].cnt;
return;
}
int mid=(l+r)/2;
build(l,mid,p*2);
build(mid+1,r,p*2+1);
push_up(p);
}
void update(int x,int d,int p=1){
if(tree[p].l==tree[p].r){
tree[p].cnt=d;
tree[p].ansl=d;
tree[p].ansr=d;
tree[p].ans=d;
return;
}
int mid=(tree[p].l+tree[p].r)/2;
if(x<=mid) update(x,d,p*2);
else update(x,d,p*2+1);
push_up(p);
}
ghj query(int p,int l,int r){
if(l<=tree[p].l && tree[p].r<=r) return tree[p];
int mid=(tree[p].l+tree[p].r)/2;
if(r<=mid) return query(p*2,l,r);
else{
if(l>mid) return query(p*2+1,l,r);//这里
else{
ghj t,a=query(p*2,l,r),b=query(p*2+1,l,r);
t.ansl=max(a.ansl,a.cnt+b.ansl);
t.ansr=max(b.ansr,a.ansr+b.cnt);
t.ans=max(max(a.ans,b.ans),a.ansr+b.ansl);
return t;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
build(1,n,1);
while(m--){
cin>>op;
if(op==1){
cin>>l>>r;
if(l>r)swap(l,r);
cout<<query(1,l,r).ans<<'\n';
}
else{
cin>>x>>d;
update(x,d);
}
}
}
给你交了一下,AC的