根号算法学习笔记
codesonic
2018-03-12 18:08:48
## 分块
### 简介
分块是一种根号数据结构
就是把一个序列划分成长度为$sqrt(n)$段处理
然后来处理问题
比如区间加和区间和问题就像线段树一样维护
### 实现
例题：[教主的魔法](https://www.luogu.org/problemnew/show/P2801)
#### block
我们先设block是每个块的大小，显然
```cpp
block=sqrt(n);
```
然后设m是块的数量，显然可能有一个块不满block个
则
```cpp
m=n/block+!!(n%block);
```
其中"!!"的作用显然是把非零数改为1
#### pos数组
为了不在使用时计算，我们再设一个数组pos，其中pos[i]表示i所在的块编号
显然对于任何一个点i
```cpp
pos[i]=(i-1)/block+1;
```
这样在调用时就方便了
#### tag数组
这个数组的作用和线段树一样
#### build函数
为了方便统计大于x的数的个数，我们可以维护每个块排序后的状态，因此可以设计一个build函数：
```cpp
inline void build(int x){
int l=(x-1)*block+1,r=min(x*block,n);
for(register int i=l;i<=r;i++)
b[i]=a[i];
sort(b+l,b+r+1);
}
```
其中x是要维护的块编号，a数组是原序列，b数组是排序后的序列。
#### 修改
修改时，若一个块包含了要修改的区间，只要O(sqrt(n))对这个区间进行遍历即可
```cpp
if(pos[l]==pos[r])
for(register int i=l;i<=r;i++)
a[i]+=v;//对单个块进行操作
```
修改区间可能不仅包含整数个块，区间左右都有可能被放在某个块的中间，所以我们需要将这左右两个块分别O(sqrt(n))遍历修改一遍，则代码如下：
```cpp
for(register int i=l;i<=pos[l]*block;i++)
a[i]+=v;//对左边的零散块进行加
for(register int i=(pos[r]-1)*block+1;i<=r;i++)
a[i]+=v;//对右边的块零散进行加
```
接着我们修改中间的整块，仅需要加tag
```cpp
for(register int i=(pos[l]+1);i<pos[r];i++)
tag[i]+=v;//对整块进行tag操作
```
我们发现经过修改后，修改区间的左右两个块不是有序的了，所以我们要在函数最后重新重构块
所以修改函数的代码为：
```cpp
inline void modify(int l,int r,int v)//修改
{
if(pos[l]==pos[r])
for(register int i=l;i<=r;i++)
a[i]+=v;//对单个块进行操作
else {
for(register int i=l;i<=pos[l]*block;i++)
a[i]+=v;//对左边的零散块进行加
for(register int i=(pos[r]-1)*block+1;i<=r;i++)
a[i]+=v;//对右边的块零散进行加
for(register int i=(pos[l]+1);i<pos[r];i++)
tag[i]+=v;//对整块进行tag操作
}
build(pos[l]);
build(pos[r]);//重构左右两个块
}
```
#### 询问函数
若一个块包含了要询问的区间，显然像刚才修改一样直接遍历
```cpp
if(pos[l]==pos[r])
for(register int i=l;i<=r;i++)
if(a[i]+tag[pos[i]]>=v)
ans++;//单个块，直接O（sqrt(n))处理
```
还是按照修改的思路，对左右两个块直接遍历处理
```cpp
for(register int i=l;i<=pos[l]*block;i++ )
if(a[i]+tag[pos[i]]>=v)
ans++;
for(register int i=(pos[r]-1)*block+1;i<=r;i++)
if(a[i]+tag[pos[i]]>=v)
ans++;
```
接着是对整块处理
```cpp
for(register int i=pos[l]+1;i<pos[r];i++)
if(b[min(i*block,n)]>=v-tag[i])//因为b经过排序了
ans+=b+min(i*block,n)-lower_bound(b+(i-1)*block+1,b+min(i*block,n),v-tag[i])+1;
```
lower_bound函数是STL中的函数，用于求一个有序区间中能够插入把一个数插入的位置，详情[百度](baidu.com)
那么整个find函数如下：
```cpp
inline int find(int l,int r,int v)//查询大于v个数
{
register int ans=0;
if(pos[l]==pos[r])
for(register int i=l;i<=r;i++)
ans+=a[i]+tag[pos[i]]>=v;//单个块，直接O（sqrt(n))处理
else {
for(register int i=l;i<=pos[l]*block;i++ )
ans+=a[i]+tag[pos[i]]>=v;//零散块
for(register int i=(pos[r]-1)*block+1;i<=r;i++)
ans+=a[i]+tag[pos[i]]>=v;//零散块
for(register int i=pos[l]+1;i<pos[r];i++)
if(b[min(i*block,n)]>=v-tag[i])//因为b经过排序了
ans+=b+min(i*block,n)-lower_bound(b+(i-1)*block+1,b+min(i*block,n),v-tag[i]) + 1;
}
return ans;
}
```
接下来是整道题的代码
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000010;
int pos[maxn],a[maxn],b[maxn],tag[maxn];//a：原数组，b：保存每个块排序后的情况；pos：在哪个块内，tag：标签,其中block和tag可以只开sqrt（n）
int block,m;
int n,q;
inline void build(int x){
int l=(x-1)*block+1,r=min(x*block,n);
for(register int i=l;i<=r;i++)
b[i]=a[i];
sort(b+l,b+r+1);//维护排序后的块
}
inline void modify(int l,int r,int v)//修改
{
if(pos[l]==pos[r])
for(register int i=l;i<=r;i++)
a[i]+=v;//对单个块进行操作
else {
for(register int i=l;i<=pos[l]*block;i++)
a[i]+=v;//对左边的零散块进行加
for(register int i=(pos[r]-1)*block+1;i<=r;i++)
a[i]+=v;//对右边的块零散进行加
for(register int i=(pos[l]+1);i<pos[r];i++)
tag[i]+=v;//对整块进行tag操作
}
build(pos[l]);
build(pos[r]);//重构左右两个块
}
inline int find(int l,int r,int v)//查询大于v个数
{
register int ans=0;
if(pos[l]==pos[r])
for(register int i=l;i<=r;i++)
ans+=a[i]+tag[pos[i]]>=v;//单个块，直接O（sqrt(n))处理
else {
for(register int i=l;i<=pos[l]*block;i++ )
ans+=a[i]+tag[pos[i]]>=v;//零散块
for(register int i=(pos[r]-1)*block+1;i<=r;i++)
ans+=a[i]+tag[pos[i]]>=v;//零散块
for(register int i=pos[l]+1;i<pos[r];i++)
if(b[min(i*block,n)]>=v-tag[i])//因为b经过排序了
ans+=b+min(i*block,n)-lower_bound(b+(i-1)*block+1,b+min(i*block,n),v-tag[i]) + 1;
}
return ans;
}
char opt[3];
int main()
{
scanf("%d %d",&n,&q);
block=sqrt(n);//每块的大小
for(register int i=1;i<=n;i++) {
scanf("%d",&a[i]);
pos[i]=(i-1)/block+1;
}
m=n/block+!!(n%block);//统计块数
for(register int i=1;i<=m;i++) build(i);
while(q--) {
scanf("%s",opt);
int l,r,w;
scanf("%d %d %d",&l,&r,&w);
if(opt[0]=='M') modify(l,r,w);
else printf("%d\n",find(l,r,w));
}
return 0;
}
```
下一道例题是[弹飞绵羊](https://www.luogu.org/problemnew/show/P3203)，一道显然是lct的题目，但是lct太难了所以我们用分块写
这一题首先还是把序列分成sqrt(n)段，然后处理即可
对于每一道分块的题目，都需要维护一些量，这些量可能是属于节点的，也可能是属于每个块的。
对于这道题，可以对每个节点维护两个变量，即还要跳几次出它所在的块和跳出块后到的节点
如何构造这两个量呢？因为是向右跳的，所以我们可以考虑递推的思想，从后往前构造：
```cpp
for(int i=n;i>=1;i--){
to[i]=i+a[i];
if(to[i]>r[pos[i]]) far[i]=1;
else {
far[i]=far[to[i]]+1;
to[i]=to[to[i]];
}
}
```
那么询问操作就很简单了，从前往后跳即可
```cpp
int ans=0;
int x;
scanf("%d",&x);
x++;
while(x<=n) {
ans+=far[x];
x=to[x];
}
printf("%d\n",ans);
```
修改操作，我们同上题一样要重新build一遍，再次对该块构造一遍那两个变量即可
```
int x,y;
scanf("%d%d",&x,&y);
x++;
a[x]=y;
for(int i=r[pos[x]];i>=l[pos[x]];i--){
to[i]=i+a[i];
if(to[i]>r[pos[i]]) far[i]=1;
else {
far[i]=far[to[i]]+1;
to[i]=to[to[i]];
}
}//重构
```
除此之外就没有什么了
## 莫队
莫队是一个暴力的算法
我们考虑一个问题
> 给出一个序列，每次询问区间中有多少不同的数
我们直接的暴力做法是$O(mn)$的，直接暴力搜索。
但是我们来想另一种做法，标记两个数左指针和右指针，每次将指针挪一个位置再统计答案
提供大致代码：
```cpp
int l=0,r=0;
for(int i=1;i<=m;i++){
int ql,qr;
scanf("%d%d",&ql,&qr);
while(l<ql)
del(l++);
while(l>ql)
add(--l);
while(r<qr)
add(++r);
while(r>qr)
del(r--);
anss[q[i].id]=ans;
}
```
因为每次移动最多移动n格，所以复杂度还是$O(mn)$，还多了辅助空间而且常数较大。
我们尝试让让他每次移动的格子少一些，于是我们考虑先将左端点排序再跑
这样的复杂度确实是降低了一些，但是还是不够低
这样
标准的莫队只能处理离线问题
（当然有带修改莫队）
其思路是将询问的区间通过某种办法排序来加快速度，听起来好像很不可靠，但其实加速起来会快很多
例题：[HH的项链](https://www.luogu.org/problemnew/show/P1972)
代码如下：
```cpp
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=500010;
struct query{
int l,r,ans,id;
}q[maxn];
int ans;
int anss[maxn];
int check[maxn]={0},color[maxn]={0};
int block;
bool cmp(query a,query b){
return (a.l/block)==(b.l/block)?a.r<b.r:a.l<b.l;
}
inline void del(int o){
--check[color[o]];
if(!check[color[o]]) ans--;
}
inline void add(int o){
if(!check[color[o]]) ans++;
++check[color[o]];
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&color[i]);
}
block=sqrt(n);
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
int l=0,r=0;
for(int i=1;i<=m;i++){
int ql=q[i].l,qr=q[i].r;
while(l<ql)
del(l++);
while(l>ql)
add(--l);
while(r<qr)
add(++r);
while(r>qr)
del(r--);
anss[q[i].id]=ans;
}
for(int i=1;i<=m;i++){
printf("%d\n",anss[i]);
}
return 0;
}
```
至于这个cmp函数为什么这么写，原因是尽量使每次移动得少，取平均最快的方法开sqrt(n)
可能是因为这样大家才说根号算法是毒瘤算法
复杂度是nsqrtm的