线段树 20pts 玄关求调

P1253 扶苏的问题

Joker_IV @ 2024-10-30 19:03:49

代码如下(AC #1 # 3)

#include <bits/stdc++.h>
using namespace std;
#define MAXN 8000010
#define int long long
#define zero -1e17
long long a[MAXN],t[MAXN],lzy[MAXN],n,q,cover[MAXN];
bool inrange(int L,int R,int l,int r){
    return l<=L&&R<=r;
}
bool outrange(int L,int R,int l,int r){
    return(l>R||r<L);
}
void build(const int u,int L,int R){
    if(L==R){
        t[u]=a[L];
        cover[u]=a[L];
        lzy[u]=0;
        return;
    }
    int mid=(R+L)>>1;
    build(u*2,L,mid);build(u*2+1,mid+1,R);
    t[u]=max(t[u*2],t[u*2+1]);
}
void maketag(int u,long long k,int type){
    if(type==1){
        t[u]=k;
        cover[u]=k;
        lzy[u]=0;
    }
    else{
        t[u]+=k;
        if(cover[u]==zero){
            lzy[u]+=k;
        }
        else{
            cover[u]+=k;
        }
    }

}
void pushdown(int u){
    if(cover[u]!=zero){
        maketag(u*2,cover[u],1);
        maketag(u*2+1,cover[u],1);
        cover[u]=zero;
    }
    else if(lzy[u]){
        maketag(u*2,lzy[u],2);
        maketag(u*2+1,lzy[u],2);
        lzy[u]=0;
    }
}
void update(int u,int L,int R,int l,int r,int k,int type){
    if(inrange(L,R,l,r) && cover[u] != zero){
        maketag(u,k,type);
        return;
    }
    if(!outrange(L,R,l,r)){
        int mid=(L+R)/2;
        pushdown(u);
        update(u*2,L,mid,l,r,k,type);update(u*2+1,mid+1,R,l,r,k,type);
        t[u]=max(t[u*2],t[u*2+1]);
    }
}
long long ask(int u,int L,int R,int l,int r){
    if(inrange(L,R,l,r))return t[u];
    if(!outrange(L,R,l,r)){
        int mid=(L+R)/2, ma = zero;
        pushdown(u);
        if (mid >=l)ma = max(ma, ask(u*2,L,mid,l,r));
        if (mid <r) ma = max(ma,ask(u*2+1,mid+1,R,l,r));
        return ma;
    }
    else return zero;
}
signed main(){
    freopen("1.in", "r", stdin);
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    while(q--){
        int x,y,k;
        int op;
        scanf("%d%d%d",&op,&x,&y);
        if(op==1||op==2){
            scanf("%d",&k);
            update(1,1,n,x,y,k,op);
        }
        else if(op==3){
            printf("%lld\n",ask(1,1,n,x,y));
        }

    }
    return 0;
}

by INKC @ 2024-11-01 22:22:14

过了吗我也遇到这个问题了

by pengbonan @ 2024-11-04 17:21:04

Cu$ $Ball

by MTEzNUc3 @ 2024-11-10 17:56:49

CuBall

by niuqichongtian @ 2024-11-14 00:17:00

20pts++

by niuqichongtian @ 2024-11-14 00:35:40

@Joker_IV 你pushdown里面

void pushdown(int u){
    if(cover[u]!=zero){
        maketag(u*2,cover[u],1);
        maketag(u*2+1,cover[u],1);
        cover[u]=zero; // 这里确定不把lzy[u]改一下？
    }
    else if(lzy[u]){
        maketag(u*2,lzy[u],2);
        maketag(u*2+1,lzy[u],2);
        lzy[u]=0;
    }
}

~~从马蜂来看，深入浅出进阶篇人手一本了~~

by niuqichongtian @ 2024-11-14 00:38:29

AC了

记录

@Joker_IV

@INKC

@pengbonan

@MTEzNUc3

by niuqichongtian @ 2024-11-14 01:10:19

发现问题了

从楼主的代码里发现：

void maketag(int u,long long k,int type){
    if(type==1){
        t[u]=k;
        cover[u]=k;
        lzy[u]=0;
    }
    else{
        t[u]+=k;
        if(cover[u]==zero){
            lzy[u]+=k;
        }
        else{
            cover[u]+=k;
        }
    }

}

这段代码当中，所有人~~包括我~~都有一个误区：type=1时，没有更新lzy[](加法tag)\ 于是就20pts

~~不要脸的求个关注~~

by niuqichongtian @ 2024-11-14 01:15:28

@niuqichongtian ~~唉不对，怎么样例都没过~~

by niuqichongtian @ 2024-11-14 02:12:29

@Joker_IV 你代码太神奇了我加了个输出，并且

void build(const int u,int L,int R){
    if(L==R){
        t[u]=a[L];
        cover[u]=a[L];
        lzy[u]=0;
        return;
    }
    int mid=(R+L)>>1;
    build(u*2,L,mid);build(u*2+1,mid+1,R);
    t[u]=max(t[u*2],t[u*2+1]);
}
void maketag(int u,long long k,int type,int k2=0){
    if(type==1){
        t[u]=k;
        cover[u]=k;
        lzy[u]=k2;
    }
    else{
        t[u]+=k;
//      if(cover[u]==zero){
            lzy[u]+=k;
//      }
//      else{
//          cover[u]+=k;
//      }
    }

}

改了

于是呼，样例对了

输出注释掉

样例错了

然后整了个

signed main(){
//  freopen("1.in", "r", stdin);
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for (int i = 1; i <= n; i++)
        ask(1, 1, n, i, i);
    build(1,1,n);
    while(q--){
        int x,y,k;
        int op;
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op==1||op==2){
            scanf("%lld",&k);
            update(1,1,n,x,y,k,op);
        }
        else if(op==3){
            printf("%lld\n",ask(1,1,n,x,y));
        }

    }
    return 0;
}

40pts,TLE一片

#include <bits/stdc++.h>
using namespace std;
#define MAXN 8000010
#define int long long
#define zero -1e17
long long a[MAXN],t[MAXN],lzy[MAXN],n,q,cover[MAXN];
bool inrange(int L,int R,int l,int r) {
    return l<=L&&R<=r;
}
bool outrange(int L,int R,int l,int r) {
    return(l>R||r<L);
}
void build(int u,int L,int R) {
    cover[u] = zero;
    lzy[u] = 0;
    if(L==R) {
        t[u]=a[L];
        cover[u]=a[L];
        lzy[u]=0;
        return;
    }
    int mid=(R+L)>>1;
    build(u*2,L,mid);
    build(u*2+1,mid+1,R);
    t[u]=max(t[u*2],t[u*2+1]);
//    printf("t[%d]=%d\n", u, t[u]);
}
void maketag(int u,long long k,int k2) {
//    if (u == 3)
//        cout << k << " " << k2 << endl;
    if(k != zero) {
        t[u]=k+k2;
        cover[u]=k;
        lzy[u]=k2;
    } else {
        t[u]+=k2;
        lzy[u]+=k2;
    }
//    if (u == 3)
//        cout << t[u] << "    I AK IOI!!! !!! !!!" << endl;
}
void pushdown(int u) {
//    if(cover[u]!=zero) {
//        maketag(u*2,cover[u],1,lzy[u]);
//        maketag(u*2+1,cover[u],1,lzy[u]);
//    } else if(lzy[u]) {
        maketag(u*2,cover[u],lzy[u]);
        maketag(u*2+1,cover[u],lzy[u]);
//    }
    cover[u]=zero;
    lzy[u]=0;
}
void update(int u,int L,int R,int l,int r,int k,int type) {
    if(inrange(L,R,l,r)) {
        if (type==1)
            maketag(u,k,0);
        else
            maketag(u,zero,k);
        return;
    }
    if(!outrange(L,R,l,r)) {
        int mid=(L+R)>>1;
        pushdown(u);
        update(u*2,L,mid,l,r,k,type);
        update(u*2+1,mid+1,R,l,r,k,type);
        t[u]=max(t[u*2],t[u*2+1]);
//        printf("t[%lld] [%lld, %lld] = %lld   when finding [%lld, %lld]\n", u, L, R, t[u], l, r);
    }
}
long long ask(int u,int L,int R,int l,int r) {
    if(inrange(L,R,l,r))return t[u];
    if(!outrange(L,R,l,r)) {
        long long mid=(L+R)/2, ma = zero;
        pushdown(u);
//        cout << cover[u] << " " << lzy[u] << " aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" << endl;
        if (mid >=l)ma = max(ma, ask(u*2,L,mid,l,r));
        if (mid <=r) ma = max(ma,ask(u*2+1,mid+1,R,l,r));
//        printf("t[%lld] [%lld, %lld] = %lld   when finding [%lld, %lld]\n", u, L, R, ma, l, r);
        return max(ask(u*2,L,mid,l,r), ask(u*2+1,mid+1,R,l,r));
    } else return zero;
}
signed main() {
//  freopen("1.in", "r", stdin);
    scanf("%lld%lld",&n,&q);
    for(int i=1; i<=n; i++)scanf("%lld",&a[i]);
    build(1,1,n);
//    for (int i = 1; i <= n; i++)
//        ask(1, 1, n, i, i);
    while(q--) {
        int x,y,k;
        int op;
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op==1||op==2) {
            scanf("%lld",&k);
            update(1,1,n,x,y,k,op);
        } else if(op==3) {
            printf("%lld\n",ask(1,1,n,x,y));
        }

    }
    return 0;
}

初始值没设！！！卡了我好长时间

最终rt

by niuqichongtian @ 2024-11-14 13:34:40

不小心多递归了一次

AC

问题总结

改进了 pushdown()，将所有的 type 都改成了直接传两个值(覆盖cover以及加法add)
maketag()$ 改为判断覆盖是否为$zero$，若是，则只加$add$；若不是，则先覆盖，再加上 $add
↑针对上面，为什么先覆盖再加法呢？因为如果add不为0，cover又不等于zero，显而易见这是pushdown调用的。则他是父节点的lazy_tag，辣么父节点要把我们覆盖，而加法一定是在cover后面来的。因为覆盖时，加法标签也会被覆盖掉，则此时我们直接覆盖cover[]和lzy[]，于是t[u] = current_cover + current_adding
针对上面的改动，同步改动了update()

看在我昨晚熬到一点多的份上给个关注

| 下一页