__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
感谢帮助,我也是那个萌新,感谢感谢,不然我都不知道要调多久