分块
数列分块入门4
- 区间修改
- 区间查询
区间修改正常。但是区间查询有几个需要注意的点:
1.需要取模。(这里对喜欢疯狂取模的人我提个醒:千万不要在 bl[l] = ...
那里取模啊,把块数给模了就完全错了,还有一些不能模的地方一定要看清楚!!!)
2.用懒标记算答案的时候一定要乘上 r-l+1
,别单点查询写多了忘记基本操作了啊。
开始讲题
这是我的部分的第一个题目,所以会讲得细一点。
分块:
数列分块算法就是把一个数列分成 \(\sqrt n\) 个块,每次处理的时候整块的用懒标记 $ O(1)$ 的时间复杂度来更新,两边的可能存在的不是整块的分散的块可以在 \(O(2 \cdot \sqrt n)\) 的时间复杂度内完成。是很优的暴力。
下面分块来讲解 分块算法。
块状数组的建立
确定块长。
大多数情况下都是取 \(\sqrt n\)
确定块的左右端点
块左端点为上一个块右端点 +1,右端点即为当前块编号乘块长。
维护块内信息
比如所属区间和区间和等内容。
len=sqrt(n);//1. 块长
for(int i=1;i<=len;i++)
L[i]=R[i-1]+1,R[i]=i*len;//2. 块端点
R[len]=n;
for(int i=1;i<=len;i++)
for(int j=L[i];j<=R[i];j++)
bel[j]=i;//3. 所属区间
初始化和之上所述基本没有变化。此时的块内信息需要维护区间和。
for(int i=1;i<=len;i++) //枚举块
for(int j=L[i];j<=R[i];j++) //枚举块内的每一位
bel[j]=i,sum[i]+=a[j]; //赋编号并统计块内和
区间加的时候分情况讨论:在整块的和不在整块的。
1.要修改的在一个块里面
if(lin==rin) {
for(int i=l;i<=r;i++)
a[i]+=k,sum[lin]+=k;
return;
}
2.要修改的不再一个块里面(一个块加上两边的不完整的块或者是好几个块):
for(int i=l;i<=R[lin];i++)//左边的零散块
sum[lin]+=k,a[i]+=k;
for(int i=L[rin];i<=r;i++)//右边的零散块
sum[rin]+=k,a[i]+=k;
for(int i=lin+1;i<rin;i++)//中间的整块
tag[i]+=k;
ps:lin和rin是开始点在的块,rin是结束点在的块。
接下来考虑区间求和。
求和的代码基本和区间修改是一样的。
我们把不再一个整块的单独用 for
循环加上。我们把整块的用懒标记乘上块的大小即可。
int query(int l ,int r, int mod) {
int lin = bl[l], rin = bl[r];
int ans=0;
if(lin==rin)
{
for(int i=l;i<=r;i++)
ans=(ans+a[i]+tag[lin])%mod;
return ans;
}
for(int i=l;i<=R[lin];i++)
ans=(ans+a[i]+tag[lin])%mod;
for(int i=L[rin];i<=r;i++)
ans=(ans+a[i]+tag[rin])%mod;
for(int i=lin+1;i<rin;i++)
ans=(ans+sum[i] + tag[i]*(R[i] - L[i] + 1))%mod;
return ans % mod;
}
由于和上面的基本一样,就不打注释了。
完整代码,注意文章一开始说的温馨提示:
#include <bits/stdc++.h>
#define int long long
#define MAXN 100005
using namespace std;
int n;
int len;
int a[MAXN];
int c;
int L[MAXN], R[MAXN];
int bl[MAXN];
int sum[MAXN];
int tag[MAXN];
void update(int l, int r, int val) {
int lin = bl[l];
int rin = bl[r];
if (lin == rin) {
for (int i = l; i <= r; ++i) {
sum[lin] += val;
a[i] += val;
}
return ;
}
for (int i = l; i <= R[lin]; ++i) {
sum[lin] += val;
a[i] += val;
}
for (int i = L[rin]; i <= r; ++i) {
sum[rin] += val;
a[i] += val;
}
for (int i = lin+1; i < rin; ++i) {
tag[i] += val;
}
return ;
}
int query(int l ,int r, int mod) {
int lin = bl[l], rin = bl[r];
int ans=0;
if(lin==rin)
{
for(int i=l;i<=r;i++)
ans=(ans+a[i]+tag[lin])%mod;
return ans;
}
for(int i=l;i<=R[lin];i++)
ans=(ans+a[i]+tag[lin])%mod;
for(int i=L[rin];i<=r;i++)
ans=(ans+a[i]+tag[rin])%mod;
for(int i=lin+1;i<rin;i++)
ans=(ans+sum[i] + tag[i]*(R[i] - L[i] + 1))%mod;
return ans % mod;
}
signed main() {
cin >> n;
len = sqrt(n);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= len; ++i) {
L[i] = (R[i - 1] + 1);
R[i] = len * i;
}
R[len] = n;
for (int i = 1; i <= len; ++i) {
for (int j = L[i]; j <= R[i]; ++j) {
bl[j] = i;
sum[i] += a[j];
}
}
for (int i = 1; i <= n; ++i) {
int opt, l ,r;
cin >> opt >> l >> r >> c;
if (opt == 0) {
update(l, r, c);
}
if (opt == 1) {
cout << query(l, r, c+ 1) % (c+1) << endl;
}
}
return 0;
}
完结散花。给个赞吧!
标签:分块,int,lin,rin,bl,MAXN From: https://www.cnblogs.com/blogs-for-Ruan-ji/p/18320788