萌新有疑问,玄关

P2801 教主的魔法

__rnfmabj__ @ 2024-07-23 15:56:05

萌新刚学分块,有一问

刚开始想的是修改了之后再直接将修改的值复制(如下代码)

void change(int x,int y,int k){
    if (belong[x]==belong[y]){
        for (int i=x;i<=y;i++)a[i]+=k,b[i]=a[i];
        sort(b+l[belong[x]],b+r[belong[x]]+1);
    } else {
        for (int i=x;i<=r[belong[x]];i++)a[i]+=k,b[i]=a[i];
        sort(b+l[belong[x]],b+r[belong[x]]+1);
        for (int i=l[belong[y]];i<=y;i++)a[i]+=k,b[i]=a[i];
        sort(b+l[belong[y]],b+r[belong[y]]+1);
        for (int i=belong[x]+1;i<=belong[y]-1;i++)lazy_tag[i]+=k;
    }
}

但是 WA 了

然后改成整段区间一起复制,再排序就对了:

void change(int x,int y,int k){
    if (belong[x]==belong[y]){
        for (int i=x;i<=y;i++)a[i]+=k;
        for(int i=l[belong[x]];i<=r[belong[x]];i++)b[i]=a[i];
        sort(b+l[belong[x]],b+r[belong[x]]+1);
    } else {
        for (int i=x;i<=r[belong[x]];i++)a[i]+=k;
        for(int i=l[belong[x]];i<=r[belong[x]];i++)b[i]=a[i];
        sort(b+l[belong[x]],b+r[belong[x]]+1);
        for (int i=l[belong[y]];i<=y;i++)a[i]+=k;
        for(int i=l[belong[y]];i<=r[belong[y]];i++)b[i]=a[i];
        sort(b+l[belong[y]],b+r[belong[y]]+1);
        for (int i=belong[x]+1;i<=belong[y]-1;i++)lazy_tag[i]+=k;
    }
}

萌新不懂这两种做法有什么区别,请神犇们帮忙解答


by qinyiyang2012 @ 2024-07-23 15:57:59

真·萌新


by UMS2 @ 2024-07-24 20:17:09

@rnfmabj 新数组中的元素顺序与原数组不同,部分修改大概率会把其他元素覆盖掉。全部修改即可避免。


by __rnfmabj__ @ 2024-07-24 20:24:27

@UMS2 谢谢大佬


by sad_lin @ 2024-08-01 09:46:57

感谢帮助,我也是那个萌新,感谢感谢,不然我都不知道要调多久


|