分块
这是一种思想，不是一种数据结构。学校题单里的题大都是用这种思想做的。
分块就是将一个序列分成多个不相交的区间，称为块。
理想块长是 \(\sqrt{n}\) ，至于为什么，它是由时间复杂度 \(O(s+\frac{n}{s})(s\)为块长\()\) 通过均值不等式算出来的。。。
定义
\(pos[i]\)：表示 \(i\) 所属的块。
\(st[i]\)：表示 \(pos[i]\) 的起始位置。
\(ed[i]\)：表示 \(pos[i]\) 的终止位置
\(sum[i]\)：表示第 \(i\) 块的总和。
点击查看代码
void build()
{
len=sqrt(n);
t=n/len;
if(n%len) t++;
for(int i=1;i<=t;i++)
{
st[i]=(i-1)*len+1;
ed[i]=i*len;
}
ed[t]=n;
for(int i=1;i<=n;i++)
{
pos[i]=(i-1)/len+1;
sum[pos[i]]+=a[i];
}
}
单点修改
直接修改即可，注意将 \(sum\) 数组也要更新。
区间修改
\(add[i]\)：表示第 \(i\) 块加的值。
- 在同一块：直接暴力修改。
- 不在同一块：零散的块暴力修改，整块修改 \(add\) 数组的值。
点击查看代码
void update(int l,int r,int k)
{
int sid=pos[l], eid=pos[r];
if(sid==eid)//在同一块
{
for(int i=l;i<=r;i++)
{
a[i]+=k;
}
sum[sid]+=(r-l+1)*k;
}
else
{
for(int i=sid+1;i<eid;i++)
{
add[i]+=k;
}
for(int i=sid;i<=ed[sid];i++)
{
a[i]+=k;
}
sum[sid]+=k*(ed[sid]-l+1);
for(int i=st[eid];i<=r;i++)
{
a[i]+=k;
}
sum[eid]+=k*(r-st[eid]+1);
}
}
区间求和
点击查看代码
int query(int l,int r)
{
int ans=0;
int sid=pos[l], eid=pos[r];
if(sid==eid)//在同一块
{
for(int i=l;i<=r;i++)
{
ans+=a[i];
}
}
else
{
for(int i=l;i<=ed[sid];i++)
{
ans+=a[i];
}
for(int i=st[eid];i<=r;i++)
{
ans+=a[i];
}
for(int i=sid+1;i<eid;i++)
{
ans+=sum[i];
}
}
return ans;
｝
区间求大于/小于/大于等于/小于等于
将每个块排序，使用二分/ \(lower\_bound\) 查询即可。
注：\(lower\_bound\) 返回的是这个序列里第一个大于等于查找的数。
点击查看代码
//区间修改，区间查询大于等于c的个数
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n, q, a[maxn];
int st[maxn], ed[maxn], pos[maxn];
int add[maxn], len;
vector<int> v[maxn];
void reset(int x)
{
v[x].clear();
for(int i=st[x];i<=ed[x];i++)
{
v[x].push_back(a[i]);
}
sort(v[x].begin(), v[x].end());
}
void build()
{
len=sqrt(n);
int t=n/len;
if(n%len) t++;
for(int i=1;i<=t;i++)
{
st[i]=(i-1)*len+1;
ed[i]=i*len;
}
ed[t]=n;
for(int i=1;i<=n;i++)
{
pos[i]=(i-1)/len+1;
v[pos[i]].push_back(a[i]);
}
for(int i=1;i<=t;i++)
{
sort(v[i].begin(),v[i].end());
}
}
void update(int l,int r,int v)
{
int sid=pos[l], eid=pos[r];
if(sid==eid)
{
for(int i=l;i<=r;i++)
{
a[i]+=v;
}
reset(sid);
}
else
{
for(int i=l;i<=ed[sid];i++)
{
a[i]+=v;
}
reset(sid);
for(int i=sid+1;i<=eid-1;i++)
{
add[i]+=v;
}
for(int i=st[eid];i<=r;i++)
{
a[i]+=v;
}
reset(eid);
}
}
int ask(int l,int r,int c)
{
int sid=pos[l], eid=pos[r];
int ans=0;
if(sid==eid)
{
for(int i=l;i<=r;i++)
{
if(a[i]+add[sid]>=c) ans++;
}
return ans;
}
else
{
for(int i=l;i<=ed[sid];i++)
{
if(a[i]+add[sid]>=c) ans++;
}
for(int i=sid+1;i<=eid-1;i++)
{
int x=lower_bound(v[i].begin(), v[i].end(), c-add[i])-v[i].begin();
ans+=(len-x);
}
for(int i=st[eid];i<=r;i++)
{
if(a[i]+add[eid]>=c) ans++;
}
return ans;
}
}
int main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build();
while(q--)
{
char opt;
int l, r, c;
cin>>opt>>l>>r>>c;
if(opt=='M')
update(l, r, c);
else
cout<<ask(l, r, c)<<endl;
}
return 0;
}
会发现用分块维护一个序列要考虑三个要素：
- 不完整的块怎么处理？
- 完整的块怎么处理？
- 要预处理什么信息？
求值函数怎么写？
- 端点在同一块：一般都是暴力处理。
- 端点不在同一块：分为角块和整块处理。
例题：
莫队
莫队是一种离线算法。且基于分块思想（一定不要忘了，否则会T的很惨）。一般不带修改，或有简单修改。
普通莫队
求区间数值种类数，暴力移动 \(l,r\) 点，暴力修改即可。根据题目调整 add 和 del 函数。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int n, m, qq, a[maxn], p[maxn], ans[maxn], t[maxn], res;
struct node{
int l, r, id;
}q[maxn];
int pos[maxn];
void build()
{
int len=sqrt(n);
for(int i=1;i<=n;i++)
{
pos[i]=(i-1)/len+1;
}
}
bool cmp(node a,node b)
{
if(pos[a.l]!=pos[b.l]) return pos[a.l]<pos[b.l];
return a.r<b.r;
}
void add(int val)
{
if(++t[val]==1) res++;
}
void del(int val)
{
if(--t[val]==0) res--;
}
signed main()
{
cin>>n>>qq;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build();
for(int i=1;i<=qq;i++)
{
int l, r;
cin>>l>>r;
q[i].id=i;
q[i].l=l;
q[i].r=r;
}
sort(q+1, q+qq+1, cmp);
int l=0, r=0;
for(int i=1;i<=qq;i++)
{
while(l>q[i].l) add(a[--l]);
while(r<q[i].r) add(a[++r]);
while(l<q[i].l) del(a[l++]);
while(r>q[i].r) del(a[r--]);
ans[q[i].id]=res;
}
for(int i=1;i<=qq;i++)
{
cout<<ans[i]<<endl;
}
return 0;
}
带修莫队
名字听着挺高级，但实际上就是在普通莫队上加入一些简单的修改。
带修莫队相比普通莫队多维护了一个时间戳，记录这是第几次修改。它的维护方式和 \(l,r\) 一样，都是将多的改回来，将少的补回去。需要注意的是 \(change\) 函数：
void change(int now,int i)
{
if(c[now].pos>=q[i].l&&c[now].pos<=q[i].r)//在区间内
{
if((++tmp[c[now].val])==1) res++;//将这个值改变,就多了一个新值,判断这个新值是否出现过
if((--tmp[a[c[now].pos]])==0) res--;////将这个值改变,就多了一个原来的值,判断这个原来的值是否还有
}
swap(c[now].val, a[c[now].pos]);//交换，便于后期使用（这里要仔细想想）
}
注意块长是 \(n^{\frac{2}{3}}\)。
点击查看代码
//带修莫队
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
struct node{
int l, r, time, id;
}q[maxn];
struct NODE{
int pos, val;
}c[maxn];
int a[maxn], ans[maxn], tmp[maxn];
int n, m, k, res;
int st[maxn], ed[maxn], pos[maxn];
int len, qnum, tim;//qnum为询问的次数，tim为修改的次数
void build()
{
len=int(pow(n, 0.66));
for(int i=1;i<=n;i++)
{
pos[i]=(i-1)/len+1;
}
}
void del(int v)
{
if((--tmp[v])==0) res--;
}
void add(int v)
{
if((++tmp[v])==1) res++;
}
void change(int now,int i)
{
if(c[now].pos>=q[i].l&&c[now].pos<=q[i].r)//在区间内
{
if((++tmp[c[now].val])==1) res++;
if((--tmp[a[c[now].pos]])==0) res--;
}
swap(c[now].val, a[c[now].pos]);//交换，便于后期使用
}
bool cmp(node x,node y)
{
if(pos[x.l]!=pos[y.l])
{
return pos[x.l]<pos[y.l];
}
if(pos[x.r]!=pos[y.r])
{
return pos[x.r]<pos[y.r];
}
if(x.time!=y.time)
{
return x.time<y.time;
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build();
for(int i=1;i<=m;i++)
{
char opt;
int x, y;
cin>>opt>>x>>y;
if(opt=='Q')
{
q[++qnum].l=x;
q[qnum].r=y;
q[qnum].time=tim;
q[qnum].id=qnum;//注意这里是qnum
}
else
{
c[++tim].pos=x;
c[tim].val=y;
}
}
sort(q+1, q+qnum+1, cmp);
int l=1, r=0, now=0;
for(int i=1;i<=qnum;i++)
{
while(l>q[i].l) add(a[--l]);
while(r<q[i].r) add(a[++r]);
while(l<q[i].l) del(a[l++]);
while(r>q[i].r) del(a[r--]);
while(now>q[i].time) change(now--, i);
while(now<q[i].time) change(++now, i);
ans[q[i].id]=res;
}
for(int i=1;i<=qnum;i++)
{
cout<<ans[i]<<endl;
}
return 0;
}