60分线段树求调/hack

bcdmwSjy @ 2023-10-18 09:49:31

#include<bits/stdc++.h>
using namespace std;
#define ls (i<<1)
#define rs (i<<1|1)
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3fll;
struct Tree {
    ll l,r,len,maxn,add,cover;
};
Tree tr[4000001];
ll a[1000001];
ll n,m;
void build(ll i,ll l,ll r) {
    tr[i].l=l;
    tr[i].r=r;
    tr[i].len=r-l+1;
    tr[i].cover=-inf;
    tr[i].add=0;
    if (l==r) {
        tr[i].maxn=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    tr[i].maxn=max(tr[ls].maxn,tr[rs].maxn);
}
void c_down(ll i){
    if (tr[i].cover!=-inf){
        tr[ls].add=tr[rs].add=0;
        tr[ls].maxn=tr[ls].maxn=tr[i].maxn;
        tr[ls].cover=tr[rs].cover=tr[i].cover;
        tr[i].cover=-inf;
    }
}
void a_down(ll i){
    if (tr[i].add){
        c_down(i);
        tr[ls].maxn+=tr[i].add;
        tr[rs].maxn+=tr[i].add;
        tr[ls].add+=tr[i].add;
        tr[rs].add+=tr[i].add;
        tr[i].add=0;
    }
}
void pushdown(ll i) {
    c_down(i);
    a_down(i);
}
void cover(ll i,ll l,ll r,ll k) {
    if (tr[i].r<l or tr[i].l>r) return;
    if (tr[i].l>=l and tr[i].r<=r) {
        tr[i].maxn=k;
        tr[i].cover=k;
        tr[i].add=0;
        return;
    }
    pushdown(i);
    if (tr[ls].r>=l) cover(ls,l,r,k);
    if (tr[rs].l<=r) cover(rs,l,r,k);
    tr[i].maxn=max(tr[ls].maxn,tr[rs].maxn);
}
void add(ll i,ll l,ll r,ll k) {
    if (tr[i].r<l or tr[i].l>r) return;
    if (tr[i].l>=l and tr[i].r<=r) {
        tr[i].maxn+=k;
        tr[i].add+=k;
        return;
    }
    pushdown(i);
    if (tr[ls].r>=l) add(ls,l,r,k);
    if (tr[rs].l<=r) add(rs,l,r,k);
    tr[i].maxn=max(tr[ls].maxn,tr[rs].maxn);
}
ll query(ll i,ll l,ll r) {
    if (tr[i].r<l or tr[i].l>r) return -inf;
    if (tr[i].l>=l and tr[i].r<=r) return tr[i].maxn;
    pushdown(i);
    ll s=-inf;
    if (tr[ls].r>=l) s=max(s,query(ls,l,r));
    if (tr[rs].l<=r) s=max(s,query(rs,l,r));
    return s;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for (ll i=1; i<=n; i++) cin>>a[i];
    build(1,1,n);
    for (ll i=0; i<m; i++) {
        ll op,x,y,k;
        cin>>op>>x>>y;
        if (op==1) {
            cin>>k;
            cover(1,x,y,k);
        } else if (op==2) {
            cin>>k;
            add(1,x,y,k);
        } else if (op==3) {
            cout<<query(1,x,y)<<"\n";
        }
    }
    return 0;
}

by bcdmwSjy @ 2023-10-18 20:53:18

发现代码中有一个 r 写成了 l ，不过还是60分

#include<bits/stdc++.h>
using namespace std;

struct IO {
#define MAXSIZE (1 << 20)
#define isd(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE],*p1,*p2;
    char pbuf[MAXSIZE],*pp;
    IO():p1(buf),p2(buf),pp(pbuf) {}
    ~IO() {
        fwrite(pbuf,1,pp-pbuf,stdout);
    }
    char gc() {
        if (p1==p2) p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin);
        return p1==p2?' ':*p1++;
    }
    bool blank(char ch) {
        return ch==' ' or ch=='\n' or ch=='\r' or ch=='\t';
    }
    template <class T>
    void read(T &x) {
        double tmp=1;
        bool sign=0;
        x=0;
        char ch=gc();
        for (; not isd(ch); ch=gc()) if (ch=='-') sign=1;
        for (; isd(ch); ch=gc()) x=(x<<1)+(x<<3)+(ch^48);
        if (ch=='.') for (ch=gc(); isd(ch); ch=gc()) tmp*=.1f,x+=tmp*(ch^48);
        if (sign) x=-x;
    }
    void read(char *s) {
        char ch=gc();
        for (; blank(ch); ch=gc());
        for (; not blank(ch); ch=gc()) *s++=ch;
        *s=0;
    }
    void read(char &c) {
        for (c=gc(); blank(c); c=gc());
    }
    void push(const char &c) {
        if (pp-pbuf==MAXSIZE) fwrite(pbuf,1,MAXSIZE,stdout),pp=pbuf;
        *pp++=c;
    }
    template <class T>
    void write(T x) {
        if (x<0) x=-x,push('-');
        static T sta[35];
        T top=0;
        do {
            sta[top++]=x%10,x/=10;
        } while (x);
        while (top) push(sta[--top]+'0');
    }
    template <class T>
    void write(T x,char end) {
        write(x),push(end);
    }
} io;

#define ls (i<<1)
#define rs (i<<1|1)
typedef long long ll;
const ll inf=1e18;
struct Tree {
    ll l,r,len,maxn,add,cover;
};
Tree tr[5000001];
ll a[1000010];
ll n,m;
void build(ll i,ll l,ll r) {
    tr[i].l=l;
    tr[i].r=r;
    tr[i].len=r-l+1;
    tr[i].cover=-inf;
    tr[i].add=0;
    if (l==r) {
        tr[i].maxn=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    tr[i].maxn=max(tr[ls].maxn,tr[rs].maxn);
}
void c_down(ll i){
    if (tr[i].cover!=-inf){
        tr[ls].add=tr[rs].add=0;
        tr[ls].maxn=tr[rs].maxn=tr[i].maxn;
        tr[ls].cover=tr[rs].cover=tr[i].cover;
        tr[i].cover=-inf;
    }
}
void a_down(ll i){
    if (tr[i].add){
        c_down(i);
        tr[ls].maxn+=tr[i].add;
        tr[rs].maxn+=tr[i].add;
        tr[ls].add+=tr[i].add;
        tr[rs].add+=tr[i].add;
        tr[i].add=0;
    }
}
void pushdown(ll i) {
    c_down(i);
    a_down(i);
}
void cover(ll i,ll l,ll r,ll k) {
    if (tr[i].r<l or tr[i].l>r) return;
    if (tr[i].l>=l and tr[i].r<=r) {
        tr[i].maxn=k;
        tr[i].cover=k;
        tr[i].add=0;
        return;
    }
    pushdown(i);
    ll mid=tr[i].l+tr[i].r>>1;
    if (l<=mid) cover(ls,l,r,k);
    if (r>mid) cover(rs,l,r,k);
    tr[i].maxn=max(tr[ls].maxn,tr[rs].maxn);
}
void add(ll i,ll l,ll r,ll k) {
    if (tr[i].r<l or tr[i].l>r) return;
    if (tr[i].l>=l and tr[i].r<=r) {
        tr[i].maxn+=k;
        tr[i].add+=k;
        return;
    }
    pushdown(i);
    ll mid=tr[i].l+tr[i].r>>1;
    if (l<=mid) add(ls,l,r,k);
    if (r>mid) add(rs,l,r,k);
    tr[i].maxn=max(tr[ls].maxn,tr[rs].maxn);
}
ll query(ll i,ll l,ll r) {
    if (tr[i].r<l or tr[i].l>r) return -inf;
    if (tr[i].l>=l and tr[i].r<=r) return tr[i].maxn;
    pushdown(i);
    ll s=-inf;
    ll mid=tr[i].l+tr[i].r>>1;
    if (l<=mid) s=max(s,query(ls,l,r));
    if (r>mid) s=max(s,query(rs,l,r));
    return s;
}
int main() {
    io.read(n),io.read(m);
    for (ll i=1; i<=n; i++) io.read(a[i]);
    build(1,1,n);
    for (ll i=0; i<m; i++) {
        ll op,x,y,k;
        io.read(op),io.read(x),io.read(y);
        if (op==1) {
            io.read(k);
            cover(1,x,y,k);
        } else if (op==2) {
            io.read(k);
            add(1,x,y,k);
        } else if (op==3) {
            io.write(query(1,x,y),'\n');
        }
    }
    return 0;
}

IO是快读快写

by bcdmwSjy @ 2023-10-19 19:30:28

调过了，其中有一个 r 写成了 l，覆盖标记下传时子树 maxn 标记应该为父节点的 cover 标记

感谢 Starstream120225 和 _mayiwei 大佬帮住我