如果用暴力来把\([l,r]\)区间内的数字都加上\(c\),肯定会超时。
这时候,我们就可以用分块。
分块基本思想
分块,顾名思义,就是把一个数组分成很多区域,对于一整块区域,可以直接用一个数组来标记这个区间一共加上了几。对于不完整的块,可以直接在\(a\)数组上进行操作。
我们需要的数组:
$\ \ \ \ \ \ \ \ \ \ $ \(block[i]\)表示\(i\)所在的块的序号。
$\ \ \ \ \ \ \ \ \ \ $ \(add[i]\)表示序号为\(i\)的区间一共加上了几
$\ \ \ \ \ \ \ \ \ \ $ \(a[i]\)表示数组\(a\)
分块代码理解
代码部分1:分区域
输入了\(a\)数组后,我们需要把这个数组进行分区域,把分到区域的序号放在\(block\)数组里。每个块的长度为\(\sqrt n\),所以,\(a[i]\)所在的区域序号为(i-1)/sqrt(n)+1
,我们把这个数放到\(block[i]\)里面就完成了第一部分的操作。
代码部分2:一个元素的大小
使用分块,我们知道,下标为\(i\)的大小由两个部分组成。一个是本身的\(a[i]\),还有一个就是存在\(add\)数组里的整块区间加上的数字。所以,它的总大小就是a[r]+add[block[r]]
代码部分3:区间加法
我们知道,区间加分为两个部分,一个是整体区域,一个不完整的部分。我们先来看不完整的部分。首先,我们进行区间加法的开始,肯定是\(l\),但是我们不知道,到底是\(r\)大,还是\(l\)所在的区域更大,所以,我们要用带\(min\)函数,来看\(l\)到\(r\)中是否有完整的部分。
for (int i = l; i <= min(r, block[l]*v); i++) { //对于不在整块区域的区间加
//block[l]*tmp l到l所在的区域结束这一小块区间
a[i] += c;
}
接着,如果\(l\)和\(r\)所处的是同一个区域,就说明,已经完成了区间加法,可以返回了。
if (block[r] == block[l]) { //l和r所处的区间是同一块
return ;
}
刚才处理的是左边部分的不完整部分,那么现在,就处理右边的不完整部分。
for (int i = (block[r] - 1) * v + 1; i <= r; i++) {
a[i] += c;
}
最后,我们进行整块的加法。因为在\(l\)之前的部分已经算过了,\(r\)所在的部分也做过了,所以,我们只需要从两个区域的中间开始完整的加法。
for (int i = block[l] + 1; i <= block[r] - 1; i++) { //l到r中间的空间
add[i] += c;
}
这题就解决了,下面是完整代码。
#include<cmath>
#include<vector>
#include<iostream>
#define endl "\n"
#define int long long
using namespace std;
const int N=50010;
int block[N],a[N],add[N];
int n,v;
//block 记录每个数字所处的块
//a 数组
//add 存每个块加上的数字
void Add(int l,int r,int c){//l~r +c
for(int i=l; i<=min(r,block[l]*v); i++){//对于不在整块区域的区间加
//block[l]*tmp l到l所在的区域结束这一小块区间
a[i]+=c;
}
if(block[r]==block[l]){//l和r所处的区间是同一块
return ;
}
for(int i=(block[r]-1)*v+1; i<=r; i++){
a[i]+=c;
}
for(int i=block[l]+1; i<=block[r]-1; i++){//l到r中间的空间
add[i]+=c;
}
return ;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
//cout.tie(0);
cin>>n;
v=sqrt(n);
for(int i=1; i<=n; i++){
cin>>a[i];
block[i]=(i-1)/v+1;//给每个数字分块
}
for(int i=1; i<=n; i++){
int opt,l,r,c;
cin>>opt>>l>>r>>c;
if(opt==0){
Add(l,r,c);
/*
cout<<"IS"<<" ";
for(int i=1; i<=n; i++){
cout<<a[i]<<" ";
}
*/
}
if(opt==1){
//add[block[r]] 储存着下标为r的数字所需要加上的数字
cout<<a[r]+add[block[r]]<<endl;
}
}
return 0;
}
标签:分块,int,add,数组,部分,block
From: https://www.cnblogs.com/wrl2010/p/17621836.html