萌新刚学OI求助！

odt03 @ 2022-08-26 12:36:25

#include<bits/stdc++.h>
using namespace std;
const long long INF=114514114514114;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-48;ch=getchar();
    }
    return x*f;
}
struct Node{
    int l,r;
    long long maxn,lazys=-INF,lazyc=-INF;
}tree[4000010];
int n,q,a[1000010];
void pushup(int p){
    tree[p].maxn=max(tree[p*2].maxn,tree[p*2+1].maxn);
}
void build(int p,int l,int r){
    tree[p].l=l,tree[p].r=r;
    if(l==r){
        tree[p].maxn=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
}
void chdown(int p){
    if(tree[p].lazyc!=-INF){
        tree[p*2].lazyc=tree[p].lazyc,tree[p*2+1].lazyc=tree[p].lazyc;
        tree[p*2].maxn=tree[p].lazyc,tree[p*2+1].maxn=tree[p].lazyc;
        tree[p].lazyc=-INF;
    }
}
void addown(int p){
    if(tree[p].lazys!=-INF){
        chdown(p);
        tree[p*2].lazys+=tree[p].lazys,tree[p*2+1].lazys+=tree[p].lazys;
        tree[p*2].maxn+=tree[p].lazys,tree[p*2+1].maxn+=tree[p].lazys;
        tree[p].lazys=-INF;
    }
}
void pushdown(int p){
    chdown(p),addown(p);
}
void upch(int p,int l,int r,int k){
    if(l>=tree[p].l&&tree[p].r<=r){
        tree[p].maxn=tree[p].lazyc=k,tree[p].lazys=0;
        return;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)/2;
    if(l<=mid)upch(p*2,l,r,k);
    if(r>mid)upch(p*2+1,l,r,k);
    pushup(p);
}
void upadd(int p,int l,int r,int k){
    if(l>=tree[p].l&&tree[p].r<=r){
        chdown(p);
        tree[p].maxn+=k,tree[p].lazys+=k;
        return;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)/2;
    if(l<=mid)upch(p*2,l,r,k);
    if(r>mid)upch(p*2+1,l,r,k);
    pushup(p);
}
long long query(int p,int l,int r){
    if(tree[p].l>=l&&tree[p].r<=r){
        return tree[p].maxn;
    }
    pushdown(p);
    long long ans=-INF;
    int mid=(tree[p].l+tree[p].r)/2;
    if(l<=mid)ans=max(query(p*2,l,r),ans);
    if(r>mid)ans=max(query(p*2+1,l,r),ans);
    return ans;
}
int main(){
    int n,q;
    n=read(),q=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    build(1,1,n);
    while(q--){
        int op,l,r,k;
        op=read(),l=read(),r=read();
        if(op==1)k=read(),upch(1,l,r,k);
        if(op==2)k=read(),upadd(1,l,r,k);
        if(op==3)printf("%lld\n",query(1,l,r));
    }
    return 0;
}

by odt03 @ 2022-08-26 12:38:09

是哪里错了

by odt03 @ 2022-08-26 12:48:36

更新了一下

#include<bits/stdc++.h>
using namespace std;
const long long INF=114514114514;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-48;ch=getchar();
    }
    return x*f;
}
struct Node{
    int l,r;
    long long maxn,lazys=-INF,lazyc=-INF;
}tree[4000010];
int n,q,a[1000010];
void pushup(int p){
    tree[p].maxn=max(tree[p*2].maxn,tree[p*2+1].maxn);
}
void build(int p,int l,int r){
    tree[p].l=l,tree[p].r=r;
    if(l==r){
        tree[p].maxn=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
}
void chdown(int p){
    if(tree[p].lazyc!=-INF){
        tree[p*2].lazyc=tree[p].lazyc,tree[p*2+1].lazyc=tree[p].lazyc;
        tree[p*2].maxn=tree[p].lazyc,tree[p*2+1].maxn=tree[p].lazyc;
        tree[p].lazyc=-INF;
    }
}
void addown(int p){
    if(tree[p].lazys){
        chdown(p);
        tree[p*2].lazys+=tree[p].lazys,tree[p*2+1].lazys+=tree[p].lazys;
        tree[p*2].maxn+=tree[p].lazys,tree[p*2+1].maxn+=tree[p].lazys;
        tree[p].lazys=-INF;
    }
}
void pushdown(int p){
    chdown(p),addown(p);
}
void upch(int p,int l,int r,int k){
    if(l>=tree[p].l&&tree[p].r<=r){
        tree[p].maxn=tree[p].lazyc=k,tree[p].lazys=0;
        return;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)/2;
    if(l<=mid)upch(p*2,l,r,k);
    if(r>mid)upch(p*2+1,l,r,k);
    pushup(p);
}
void upadd(int p,int l,int r,int k){
    if(l>=tree[p].l&&tree[p].r<=r){
        chdown(p);
        tree[p].maxn+=k,tree[p].lazys+=k;
        return;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)/2;
    if(l<=mid)upch(p*2,l,r,k);
    if(r>mid)upch(p*2+1,l,r,k);
    pushup(p);
}
long long query(int p,int l,int r){
    if(tree[p].l>=l&&tree[p].r<=r){
        return tree[p].maxn;
    }
    pushdown(p);
    long long ans=-INF;
    int mid=(tree[p].l+tree[p].r)/2;
    if(l<=mid)ans=max(query(p*2,l,r),ans);
    if(r>mid)ans=max(query(p*2+1,l,r),ans);
    return ans;
}
int main(){
    int n,q;
    n=read(),q=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    build(1,1,n);
    while(q--){
        int op,l,r,k;
        op=read(),l=read(),r=read();
        if(op==1)k=read(),upch(1,l,r,k);
        if(op==2)k=read(),upadd(1,l,r,k);
        if(op==3)printf("%lld\n",query(1,l,r));
    }
    return 0;
}

by odt03 @ 2022-08-26 12:48:51

但还是之前那样

by WanderingTrader @ 2022-08-26 12:49:30

@himxx 个人猜测是inf的初始值溢出了，影响了答案，应该是

const long long INF=114514114514114LL; //注意这个LL

by _youdu666_ @ 2022-08-26 12:52:05

草，现在刚学oi的都会线段树了

by odt03 @ 2022-08-26 12:52:26

@WanderingTrader 不是这个原因

by odt03 @ 2022-08-26 12:56:18

不要在意标题。

by odt03 @ 2022-08-26 15:48:45

#include<bits/stdc++.h>
using namespace std;
const long long INF=114514114514;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-48;ch=getchar();
    }
    return x*f;
}
struct Node{
    int l,r;
    long long maxn,lazys,lazyc;
}tree[4000010];
int n,q,a[1000010];
void pushup(int p){
    tree[p].maxn=max(tree[p*2].maxn,tree[p*2+1].maxn);
}
void build(int p,int l,int r){
    tree[p].l=l,tree[p].r=r;
    if(l==r){
        tree[p].maxn=a[l],tree[p].lazyc=-INF;
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
}
void chdown(int p){
    if(tree[p].lazyc!=-INF){
        tree[p*2].lazys=tree[p*2+1].lazys=0;
        tree[p*2].maxn=tree[p].lazyc,tree[p*2+1].maxn=tree[p].lazyc;
        tree[p*2].lazyc=tree[p].lazyc,tree[p*2+1].lazyc=tree[p].lazyc;
        tree[p].lazyc=-INF;
    }
}
void addown(int p){
    if(tree[p].lazys){
        chdown(p);
        tree[p*2].maxn+=tree[p].lazys,tree[p*2+1].maxn+=tree[p].lazys;
        tree[p*2].lazys+=tree[p].lazys,tree[p*2+1].lazys+=tree[p].lazys;
        tree[p].lazys=0;
    }
}
void pushdown(int p){
    chdown(p);addown(p);
}
void upch(int p,int l,int r,int k){
    if(l>=tree[p].l&&tree[p].r<=r){
        tree[p].maxn=tree[p].lazyc=k,tree[p].lazys=0;
        return;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)/2;
    if(l<=mid)upch(p*2,l,r,k);
    if(r>mid)upch(p*2+1,l,r,k);
    pushup(p);
}
void upadd(int p,int l,int r,int k){
    if(l>=tree[p].l&&tree[p].r<=r){
        chdown(p);
        tree[p].maxn+=k,tree[p].lazys+=k;
        return;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)/2;
    if(l<=mid)upadd(p*2,l,r,k);
    if(r>mid)upadd(p*2+1,l,r,k);
    pushup(p);
}
long long query(int p,int l,int r){
    if(tree[p].l>=l&&tree[p].r<=r){
        return tree[p].maxn;
    }
    pushdown(p);
    long long ans=-INF;
    int mid=(tree[p].l+tree[p].r)/2;
    if(l<=mid)ans=max(query(p*2,l,r),ans);
    if(r>mid)ans=max(query(p*2+1,l,r),ans);
    return ans;
}
int main(){
    int n,q;
    n=read(),q=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    build(1,1,n);
    while(q--){
        int op,l,r,k;
        op=read(),l=read(),r=read();
        if(op==1)k=read(),upch(1,l,r,k);
        if(op==2)k=read(),upadd(1,l,r,k);
        if(op==3)printf("%lld\n",query(1,l,r));
    }
    return 0;
}
``

update.

by odt03 @ 2022-08-26 16:00:05

#include<bits/stdc++.h>
using namespace std;
const long long INF=114514114514;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-48;ch=getchar();
    }
    return x*f;
}
struct Node{
    int l,r;
    long long maxn,lazys,lazyc;
}tree[4000010];
int n,q,a[1000010];
void pushup(int p){
    tree[p].maxn=max(tree[p*2].maxn,tree[p*2+1].maxn);
}
void build(int p,int l,int r){
    tree[p].l=l,tree[p].r=r;
    if(l==r){
        tree[p].maxn=a[l],tree[p].lazyc=-INF;
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
}
void chdown(int p){
    if(tree[p].lazyc!=-INF){
        tree[p*2].lazys=tree[p*2+1].lazys=0;
        tree[p*2].maxn=tree[p].lazyc,tree[p*2+1].maxn=tree[p].lazyc;
        tree[p*2].lazyc=tree[p].lazyc,tree[p*2+1].lazyc=tree[p].lazyc;
        tree[p].lazyc=-INF;
    }
}
void addown(int p){
    if(tree[p].lazys){
        chdown(p);
        tree[p*2].maxn+=tree[p].lazys,tree[p*2+1].maxn+=tree[p].lazys;
        tree[p*2].lazys+=tree[p].lazys,tree[p*2+1].lazys+=tree[p].lazys;
        tree[p].lazys=0;
    }
}
void pushdown(int p){
    chdown(p);addown(p);
}
void upch(int p,int l,int r,int k){
    if(l>=tree[p].l&&tree[p].r<=r){
        tree[p].maxn=tree[p].lazyc=k,tree[p].lazys=0;
        return;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)/2;
    if(l<=mid)upch(p*2,l,r,k);
    if(r>mid)upch(p*2+1,l,r,k);
    pushup(p);
}
void upadd(int p,int l,int r,int k){
    if(l>=tree[p].l&&tree[p].r<=r){
        chdown(p);
        tree[p].maxn+=k,tree[p].lazys+=k;
        return;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)/2;
    if(l<=mid)upadd(p*2,l,r,k);
    if(r>mid)upadd(p*2+1,l,r,k);
    pushup(p);
}
long long query(int p,int l,int r){
    if(l>=tree[p].l&&tree[p].r<=r){
        return tree[p].maxn;
    }
    pushdown(p);
    long long ans=-INF;
    int mid=(tree[p].l+tree[p].r)/2;
    if(l<=mid)ans=max(ans,query(p*2,l,r));
    if(r>mid)ans=max(ans,query(p*2+1,l,r));
    return ans;
}
int main(){
    int n,q;
    n=read(),q=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    build(1,1,n);
    while(q--){
        int op,l,r,k;
        op=read(),l=read(),r=read();
        if(op==1)k=read(),upch(1,l,r,k);
        if(op==2)k=read(),upadd(1,l,r,k);
        if(op==3)printf("%lld\n",query(1,l,r));
    }
    return 0;
}

by odt03 @ 2022-08-26 16:00:33

很好实在调不出来了