萌新有疑问,玄关
查看原帖
萌新有疑问,玄关
914275
__rnfmabj__楼主2024/7/23 15:56

萌新刚学分块,有一问

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

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;
	}
}

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

2024/7/23 15:56
加载中...