萌新刚学分块,有一问
刚开始想的是修改了之后再直接将修改的值复制(如下代码)
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;
}
}
萌新不懂这两种做法有什么区别,请神犇们帮忙解答