一个小小线段树懒标记下传疑问求教

P1253 扶苏的问题

Dangerise @ 2024-01-23 19:49:17

这是一道简单线段树的题目,为节省各位时间,以下简述题目大意

题目要求支持三种操作

  1. 区间加某个数
  2. 区间设定为某个数
  3. 查询某个元素

50pts代码如下

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

typedef long long ll;

inline ll qread() {
    ll ans=0;
    char c=getchar();
    bool f=0;
    while(c<'0'||c>'9') {
        if(c=='-') {
            f=1;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        ans=ans*10+c-'0';
        c=getchar();
    }
    if(f) {
        return -ans;
    } else {
        return ans;
    }
}

struct Node {
    int l,r;
};
Node nodes[4004000];
ll add_tag[4004000];
ll set_to[4004000];
bool set_tag_exist[4004000];
ll maxn[4004000];
inline int left_child(int x) {
    return x<<1;
}
inline int right_child(int x) {
    return (x<<1)|1;
}
inline int node_size(int x) {
    return nodes[x].r-nodes[x].l+1;
}
inline int middle(int x) {
    return (nodes[x].l+nodes[x].r)>>1;
}

ll ini[4004000];
int n,m;

inline void build(int node,int l,int r) {
    nodes[node].l=l;
    nodes[node].r=r;

    if(l==r) {
        maxn[node]=ini[l];
        return;
    }

    int mid=middle(node);
    build(left_child(node),l,mid);
    build(right_child(node),mid+1,r);
    maxn[node]=max(maxn[left_child(node)],maxn[right_child(node)]);
}

inline void tad(int node,int x) {
    if(set_tag_exist[node]) {
        set_to[node]+=x;
    } else {
        add_tag[node]+=x;
    }
    maxn[node]+=x;
}

inline void pushdown(int node) {
    int l=left_child(node),r=right_child(node);
    if(add_tag[node]) {
        tad(l,add_tag[node]);
        tad(r,add_tag[node]);
        add_tag[node]=0;
    }
    if(set_tag_exist[node]) {
        add_tag[l]=add_tag[r]=0;
        set_to[l]=set_to[r]=set_to[node];
        set_tag_exist[l]=set_tag_exist[r]=1;
        maxn[l]=maxn[r]=set_to[node];
        set_to[node]=set_tag_exist[node]=0;
    }
}

int a,b;
ll v;
inline void add_opt(int node) {
    int l=nodes[node].l,r=nodes[node].r;
    if(a<=l&&r<=b) {
        tad(node,v);
        return;
    }

    pushdown(node);
    int mid=middle(node);
    if(a<=mid) {
        add_opt(left_child(node));
    }
    if(mid<b) {
        add_opt(right_child(node));
    }
    maxn[node]=max(maxn[left_child(node)],maxn[right_child(node)]);
}

inline void set_opt(int node) {
    int l=nodes[node].l,r=nodes[node].r;
    if(a<=l&&r<=b) {
        add_tag[node]=0;
        set_tag_exist[node]=1;
        set_to[node]=v;
        maxn[node]=v;
        return;
    }

    pushdown(node);
    int mid=middle(node);
    if(a<=mid) {
        set_opt(left_child(node));
    }
    if(mid<b) {
        set_opt(right_child(node));
    }
    maxn[node]=max(maxn[left_child(node)],maxn[right_child(node)]);
}

const ll llmin=-0x3f3f3f3f3f3f3f3f;
inline ll query(int node) {
    int l=nodes[node].l,r=nodes[node].r;
    if(a<=l&&r<=b) {
        return maxn[node];
    }

    pushdown(node);
    int mid=middle(node);
    ll ans=llmin;
    if(a<=mid) {
        ll t=query(left_child(node));
        ans=t;
    }
    if(mid<b) {
        ll t=query(right_child(node));
        ans=max(ans,t);
    }
    return ans;
}

int main() {
    n=qread(),m=qread();
    for(int i=1; i<=n; i++) {
        ini[i]=qread();
    }
    build(1,1,n);
    for(int i=1; i<=m; i++) {
        int p=qread();
        if(p==1) {
            a=qread(),b=qread(),v=qread();
            set_opt(1);
        } else if(p==2) {
            a=qread(),b=qread(),v=qread();
            add_opt(1);
        } else {
            a=qread(),b=qread();
            ll ans=query(1);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

问题在于下放标记的操作,当某个节点将要添加一个add的标记时,我认为,如果已经存在set的标记,可以直接将set标记的值加上将要加上的add标记的值,就不需要添加add标记了

inline void tad(int node,int x) {
    if(set_tag_exist[node]) {
        set_to[node]+=x;
    } else {
        add_tag[node]+=x;
    }
    maxn[node]+=x;
}

而题解的做法是现将当前set标记下传,再为当前节点添加add标记,请问我的想法有何问题?

AC代码,并且还有一个疑问

inline void tad(int node,int x) {
    add_tag[node]+=x;
    maxn[node]+=x;
}

inline void pushdown(int node) {
    int l=left_child(node),r=right_child(node);
    if(set_tag_exist[node]) {
        add_tag[l]=add_tag[r]=0;
        set_to[l]=set_to[r]=set_to[node];
        set_tag_exist[l]=set_tag_exist[r]=1;
        maxn[l]=maxn[r]=set_to[node];
        set_to[node]=set_tag_exist[node]=0;
    }
    if(add_tag[node]) {
//      tad(l,add_tag[node]);
//      tad(r,add_tag[node]);
        add_tag[l]+=add_tag[node];
        add_tag[r]+=add_tag[node];
        maxn[l]+=add_tag[node];
        maxn[r]+=add_tag[node];
        //为什么以上4行代码不能 替换成注释中的代码呢?
        add_tag[node]=0;
    }
}

by 杜都督 @ 2024-01-30 04:10:59

大致看了一下,如果说得不对欢迎指正

关于疑问1:根据逻辑可以推断出set和add两个tag不可能同时出现,所以你原来tad()中的if判断完全多余

关于疑问2:因为add_tag[node]是ll,但你tad()的x是int,导致传参之后精度损失


|