社区讨论
分块代码过线段树模板过不了,求大佬指导
灌水区参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo9ln8gn
- 此快照首次捕获于
- 2023/10/28 13:26 2 年前
- 此快照最后确认于
- 2023/10/28 13:26 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;
#define int long long
int n,s,st[maxn],ed[maxn],size[maxn],belong[maxn],a[maxn],data[maxn],mark[maxn];//a原数据,data为维护的值(此处为区间和),mark为标记整块的加法
void change(int x,int y,int k){//区间修改
if(belong[x]=belong[y]){
for(int i=x;i<=y;i++){
a[i]+=k;//原数据数组加
data[belong[i]]+=k;//维护的区间和加
}
}//当x与y在同一块内时,直接暴力修改原数组和data数组
if(belong[x]!=belong[y])
{
for(int i=x;i<=ed[belong[x]];++i){
a[i]+=k;
data[belong[i]]+=k;
}
for(int i=st[belong[y]];i<=y;i++){
a[i]+=k;
data[belong[i]]+=k;
}//否则,先暴力修改左右两边的零散区间:
for(int i=belong[x]+1;i<belong[y];i++){
mark[i]+=k;
}//然后对中间的整块打上标记:
}//
}
int requst(int x,int y){
if(belong[x]=belong[y]){
for(int i=x;i<=y;i++){
s+=(a[i]+mark[belong[i]]);
}
}//同样地,如果左右两边在同一块,直接暴力计算区间和。
if(belong[x]!=belong[y])
{
for(int i=x;i<=ed[belong[x]];++i){
s+=(a[i]+mark[belong[i]]);
}
for(int i=st[belong[y]];i<=y;i++){
s+=(a[i]+mark[belong[i]]);
}//否则,暴力计算零碎块
for(int i=belong[x]+1;i<belong[y];i++){
s+=(data[i]+mark[i]*size[i]);//再处理整块:
}
}
return s;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int sq=sqrt(n);
for(int i=1;i<=sq;++i){
st[i]=n/sq*(i-1)+1;
ed[i]=n/sq*i;
}
ed[sq]=n;
for(int i=1;i<=sq;i++){
for(int j=st[i];j<=ed[i];j++){
belong[j]=i;//下标为j的数属于块i
}
}
for(int i=1;i<=sq;i++){
for(int j=st[i];j<=ed[i];i++){
data[i]+=a[j];//第i块求和
}
}
for (int i = 1; i <= sq; ++i)
size[i] = ed[i]-st[i] + 1;
int op;
cin>>op;
if(op==1){
int x,y,k;
cin>>x>>y>>k;
change(x,y,k);
}
if(op==2){
int x,y;
cin>>x>>y;
cout<<requst(x,y)<<endl;
}
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...