分块(一)
- 2022 年 11 月 10 日
- 筆記
分块(一)
优雅的暴力~~
一、一些题目
基本思想:
将原序列划分成 \(\sqrt n\) 个块,记录每一个元素对应其所在块的编号,统计每个块的信息。
(至于为什么是 \(\sqrt n\),下面会讲到~~)
这里,我们用 \(id\) 表示每个元素对应块的编号,每一块的长度为 \(len\),具体如下:
当 \(i\in[1,len]\) 时,\(id[i]=1\);
当 \(i\in[len+1,2\times len]\) 时,\(id[i]=2\);
……
当 \(i\in[(len-1)\times len+1,n]\) 时,\(id[i]=n/len+1\)。
scanf("%d",&n);
len=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
id[i]=(i-1)/len+1;
}
Tips: 关于 \(id[i]\) 的计算
i-1
是为了保证第一个块有 \(len\) 个元素,而不是 \(len-1\) 个;+1
是为了让第一个块的编号为 \(1\),而不是 \(0\)。
对于每一个区间操作,分为如下两种情况:
-
左右端点在同一个块中,枚举整个区间暴力求解
-
左右端点在不同的块中:
① 对于能完全包含在内的块,我们称为完整块,直接利用这个块预处理的信息,\(O(1)\) 得到答案;
② 对于区间两端不能涵盖的整块,我们称为不完整块,暴力枚举求解即可。
两个操作的时间复杂度最优为 \(O(\sqrt n)\)。
有一张图,或许能帮助你理解:
关于 \(\sqrt n\) 的小证明:
需要一点高中数学知识:(真的只有一点,不是亿点)
基本不等式:\(\cfrac {a+b} 2 \geq \sqrt {ab}\),当且仅当 \(a=b\) 时,等号成立。
-
左右端点在同一个块中,暴力枚举整个块,复杂度最坏为 \(O(len)\);
-
左右端点不在同一个块中,答案由三部分组成:以 \(l\) 开偷的不完整块、中间几个完整块、以 \(r\) 结尾的不完整块。
① 对于完整块,时间复杂度为 \(O(\cfrac n {len})\);
② 对于不完整块,时间复杂度为 \(O(len)\)
故最坏复杂度的和为 \(O(\cfrac n {len} + len)\),由基本不等式可得:
\(\cfrac n {len} + len \geq 2\sqrt{\cfrac n {len} \times len} = 2 \sqrt n\),当且仅当 \(\cfrac n {len} = len\),即 \(len=\sqrt n\) 时,等号成立。
也就是单次操作的时间复杂最优,为 \(O(\sqrt n)\),此时块长也为 \(\sqrt n\)。
既然基本思想已经知道了,那就来 “亿”点点 例题实践一下吧:
Example1: 数列分块入门1 LibreOJ #6277
给出一个长为 \(n\) 的数列,以及 \(n\) 个操作,操作涉及区间加法,单点查值。
-
区间增加
我们可以对于每一个块,按照分块的基本思想进行累加即可:
- 对于 完整块,利用数组 \(b\) 存储对于块整体加的值,不必对于每一个 \(a[i]\) 做加法;
- 对于 不完整块 或 左右端点在同一个块中,暴力枚举,对 \(a[i]\) 做加法即可。
void add(int l,int r,int v)
{
int lid=id[l],rid=id[r]; // 左右两端点对于块的编号
if(lid==rid) // 左右端点在同一个块中
{
for(int i=l;i<=r;i++) // 暴力加
a[i]+=v;
return;
}
for(int i=l;id[i]==lid;i++) // 以l开头的不完整块,暴力加
a[i]+=v;
for(int i=lid+1;i<rid;i++) // 完整块,直接改变b的值
b[i]+=v;
for(int i=r;id[i]==rid;i--) // 以r结尾的不完整块,暴力加
a[i]+=v;
}
Tips:
- 对于完整块的操作,
for
中的 \(i\) 表示块的编号,而不是元素的编号; - 若 \(a\) 的下标为 \(i\),则 \(b\) 的下标为 \(id[i]\)。
-
单点查询
直接输出本身的值 \(a[i]\) 与 该元素所在块的 \(b[id[i]]\)。
int ask(int l,int r)
{
return a[r]+b[id[r]];
}
Example2: 数列分块入门2 LibreOJ #6278
给出一个长为 \(n\) 的数列,以及 \(n\) 个操作,操作涉及区间加法,询问区间内小于某个值 \(x\) 的元素个数。
相较于上一题,多了区间查询。
-
区间查询
看到 小于 \(x\) 的个数,直接想到二分
这道题中,我们可以 用
vector
存储每一个块所有元素的值,方便进行二分查找。
- 对于 完整块,二分对应块的全部元素,统计个数;
- 对于 不完整块 或 左右端点在同一个块中,暴力枚举,统计 \(a[i]<v\) 的个数。
int clac(int x,int v) // 手写二分需要此函数
{
int l=0,r=vec[x].size();
while(l+1<r)
{
int mid=l+r>>1;
if(vec[x][mid]+b[x]<v) l=mid; // 别忘记加b数组的值
else r=mid;
}
if(vec[x][l]+b[x]<v) return l+1; //vector从0开始存储,数组从1开始存储,+1保证下标对应
else if(vec[x][r]+b[x]<v) return r+1;
else return 0;
}
int ask(int l,int r,int v)
{
int lid=id[l],rid=id[r],res=0;
if(lid==rid)
{
for(int i=l;i<=r;i++)
if(a[i]+b[id[i]]<v) res++;
return res;
}
for(int i=l;id[i]==lid;i++)
if(a[i]+b[id[i]]<v) res++;
for(int i=lid+1;i<rid;i++)
res+=clac(i,v); // 手写二分,下面为STL
// res+=lower_bound(vec[i].begin(),vec[i].end(),v-b[i])-vec[i].begin();
for(int i=r;id[i]==rid;i--)
if(a[i]+b[id[i]]<v) res++;
return res;
}
-
区间增加
由于块用
vector
存了起来,所以每一次按照正常单点增加的造作之后,更新一下对应vector
。
void change(int x)
{
vec[x].clear();
int l=(x-1)*len+1,r=min(x*len,n);
for(int i=l;i<=r;i++)
vec[x].push_back(a[i]);
sort(vec[x].begin(),vec[x].end());
}
void add(int l,int r,int v)
{
int lid=id[l],rid=id[r];
if(lid==rid)
{
for(int i=l;i<=r;i++)
a[i]+=v;
change(lid);
return;
}
for(int i=l;id[i]==lid;i++)
a[i]+=v;
change(lid);
for(int i=lid+1;i<rid;i++)
b[i]+=v;
for(int i=r;id[i]==rid;i--)
a[i]+=v;
change(rid);
}
-
初始化
其实也没有什么变化,多存一个
vector
即可。
scanf("%d",&n);
len=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
id[i]=(i-1)/len+1;
vec[id[i]].push_back(a[i]);
}
Example3: 数列分块入门3 LibreOJ #6279
给出一个长为 \(n\) 的数列,以及 \(n\) 个操作,操作涉及区间加法,询问区间内小于某个值 \(x\) 的前驱(比其小的最大元素)。
区间增加和上题一样,区间查询的时候,将二分答案的返回值更改为当前元素的值即可。
int get(int x,int v)
{
int l=0,r=vec[x].size();
while(l+1<r)
{
int mid=l+r>>1;
if(vec[x][mid]+b[x]<v) l=mid;
else r=mid;
}
if(vec[x][l]+b[x]<v) return vec[x][l]+b[x];
else if(vec[x][r]+b[x]<v) return vec[x][r]+b[x];
else return -1; // 当前块中没有<v的数,返回-1
}
int ask(int l,int r,int v)
{
int lid=id[l],rid=id[r],ans=-1;
if(lid==rid)
{
for(int i=l;i<=r;i++)
if(a[i]+b[lid]<v) ans=max(ans,a[i]+b[lid]);
return ans;
}
for(int i=l;id[i]==lid;i++)
if(a[i]+b[lid]<v) ans=max(ans,a[i]+b[lid]);
for(int i=lid+1;i<rid;i++)
ans=max(ans,get(i,v));
for(int i=r;id[i]==rid;i--)
if(a[i]+b[rid]<v) ans=max(ans,a[i]+b[rid]);
return ans;
}
Example4: 数列分块入门4 LibreOJ #6280
给出一个长为 \(n\) 的数列,以及 \(n\) 个操作,操作涉及区间加法,区间求和。
在这道题中,我们再引用一个 数组 \(s\) ,\(s[i]\) 表示 第 \(i\) 个块的数值和。
因此在预处理的时候,需要更新一下数组 \(s\):
scanf("%d",&n);
len=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
id[i]=(i-1)/len+1;
s[id[i]]+=a[i];
}
-
区间增加
注意在增加的时候及时更改数组 \(s\) 的值。
void add(int l,int r,int v)
{
int lid=id[l],rid=id[r];
if(lid==rid)
{
for(int i=l;i<=r;i++)
a[i]+=v,s[lid]+=v;
return;
}
for(int i=l;id[i]==lid;i++)
a[i]+=v,s[lid]+=v;
for(int i=lid+1;i<rid;i++)
b[i]+=v,s[i]+=(LL)v*len; // 一个块有len个元素,每个元素增加v。共增加v*len
for(int i=r;id[i]==rid;i--)
a[i]+=v,s[rid]+=v;
}
- 区间求和
- 对于 完整块,直接返回数组 \(s\) 的值即可;
- 对于 不完整块 或 左右端点在同一个块中,暴力枚举每一个点,累加每一个点的值。
LL ask(int l,int r,int p)
{
LL res=0;
int lid=id[l],rid=id[r];
if(lid==rid)
{
for(int i=l;i<=r;i++)
res=(LL)(res+a[i]+b[lid])%p;
return res;
}
for(int i=l;id[i]==lid;i++)
res=(LL)(res+a[i]+b[lid])%p;
for(int i=lid+1;i<rid;i++)
res=(LL)(res+s[i])%p;
for(int i=r;id[i]==rid;i--)
res=(LL)(res+a[i]+b[rid])%p;
return res;
}
Example5: 数列分块入门5 LibreOJ #6281
给出一个长为 \(n\) 的数列 \(a_1 ,\ldots, a_n\),以及 \(n\) 个操作,操作涉及区间开方,区间求和。
-
区间开方
我们知道,开方操作能使数值快速减小。
故可以引用 数组 \(tag\) 用来标记每一个块的所有元素是否全部变为 \(1\),
如果全都变为 \(1\) 了,之后再进行开方操作就可以跳过,优化时间复杂度。
由于本题仍需区间求和,开方的时候不方便直接更改 数组 \(s\) 的值,
因此我们可以在更改 \(a[i]\) 的时候,先减去 \(a[i]\),再将开方过后的值加到 数组\(s\) 中。
void change(int l,int r)
{
int lid=id[l],rid=id[r];
if(lid==rid)
{
for(int i=l;i<=r;i++)
{
if(tag[lid]) break; // 该块全部为1.开方操作没有任何作用,直接跳过
s[lid]-=a[i]; // 先减去原本元素的值
a[i]=sqrt(a[i]);
s[lid]+=a[i]; // 加上开方之后该元素的值
}
return;
}
for(int i=l;id[i]==lid;i++)
{
if(tag[lid]) break;
s[lid]-=a[i];
a[i]=sqrt(a[i]);
s[lid]+=a[i];
}
for(int i=lid+1;i<rid;i++)
{
if(tag[i]) continue; // 注意这里不能break!!!
tag[i]=true; s[i]=0;
for(int j=(i-1)*len+1;j<=min(i*len,n);j++)
{
a[j]=sqrt(a[j]);
s[i]+=a[j];
if(a[j]>1) tag[i]=false; // 有一个元素>1,就为false;只有全部为1的时候,才是true
}
}
for(int i=r;id[i]==rid;i--)
{
if(tag[rid]) break;
s[rid]-=a[i];
a[i]=sqrt(a[i]);
s[rid]+=a[i];
}
}
-
区间求和
由于没有增加操作,也就不必统计数组 \(b\)。
int ask(int l,int r)
{
int lid=id[l],rid=id[r],res=0;
if(lid==rid)
{
for(int i=l;i<=r;i++)
res+=a[i];
return res;
}
for(int i=l;id[i]==lid;i++)
res+=a[i];
for(int i=lid+1;i<rid;i++)
res+=s[i];
for(int i=r;id[i]==rid;i--)
res+=a[i];
return res;
}
Example6: 数列分块入门6 LibreOJ #6282
给出一个长为 \(n\) 的数列,以及 \(n\) 个操作,操作涉及单点插入,单点询问,数据随机生成。
-
单点插入
对于单点插入,显然之前用的分块方法不太可行了。
这时,我们可以利用
vector
可以插入元素的特性,将每一个块都存到一个堆中。对于每一个插入操作,找到插入位置对应的块以及在块中的位置即可。
typedef pair<int,int> PII;
PII get(int x) // 找到插入位置对应的块以及位置
{
int cnt=0,i; // cnt表示前面的块共有多少个元素,i表示此时在第几个块
for(i=1;cnt+vec[i].size()<x;i++) // 只要这个块仍然到达不了位置x
cnt+=vec[i].size(); // 加上这个块的长度
return {i,x-cnt}; // x-cnt就是位置x,是第i个块的第几个元素
}
void add(int x,int v)
{
PII t=get(x);
vec[t.first].insert(vec[t.first].begin()+t.second-1,v);
// 由于要在x前面增加新元素v,故要-1
}
-
单点查询
有了插入的基础,查询就非常容易了。
还是利用 \(get\) 函数找到 对应的块以及在块中的位置即可。
int ask(int x)
{
PII t=get(x);
return vec[t.first][t.second-1];
}
-
初始化
由于块都存到了
vector
中,就不需要 数组 \(id\) 记录每一个元素对应块的编号了。
scanf("%d",&n);
len=sqrt(n);
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d",&x);
y=(i-1)/len+1;
vec[y].push_back(x);
}
Example7: 数列分块入门7 LibreOJ #6283
给出一个长为 n 的数列,以及 n 个操作,操作涉及区间乘法,区间加法,单点询问。
利用 线段树延迟标记 的思想(既然都学分块了,就一定会线段树吧(~ ̄▽ ̄)~)
用 \(add\_tag[i]\) 表示第 \(i\) 个块整体增加的值,\(mul\_tag[i]\) 表示第 \(i\) 个块整体乘的值
每次对 不完整块 进行处理时,将标记下传给元素本身,在进行操作即可。
由于 加法和乘法 混合进行,为了保证下传标记次数不变,
我们可以让每一次进行乘法操作时,同时将 \(add\_tag\) 的值也进行乘法运算。
void spread(int x)
{
int l=(x-1)*len+1,r=min(x*len,n);
for(int i=l;i<=r;i++)
a[i]=Add(Pow(a[i],mul_tag[x]),add_tag[x]);
// 每次乘法进行处理之后,返回给元素的值就要先乘后加了,因为加的值以及乘过了
// 下传操作完成之后,清空所有标记数组
add_tag[x]=0; // 加法初值为0
mul_tag[x]=1; // 乘法初值为1
}
Tips: Add
与 Pow
函数:在函数中进行 \(\bmod\) 运算,防止代码中部分运算忘记 \(\bmod\),导致最终结果错误。
inline int Add(int a,int b)
{
return a+b>=Mod?a+b-Mod:a+b;
}
inline int Pow(int a,int b)
{
return (LL)a*b%Mod;
}
- 区间加法
void add(int l,int r,int v)
{
int lid=id[l],rid=id[r];
if(lid==rid)
{
spread(lid);
for(int i=l;i<=r;i++)
a[i]=Add(a[i],v);
return;
}
spread(lid);
for(int i=l;id[i]==lid;i++)
a[i]=Add(a[i],v);
for(int i=lid+1;i<rid;i++)
add_tag[i]=Add(add_tag[i],v);
spread(rid);
for(int i=r;id[i]==rid;i--)
a[i]=Add(a[i],v);
}
- 区间乘法
void mul(int l,int r,int v)
{
int lid=id[l],rid=id[r];
if(lid==rid)
{
spread(lid);
for(int i=l;i<=r;i++)
a[i]=Pow(a[i],v);
return;
}
spread(lid);
for(int i=l;id[i]==lid;i++)
a[i]=Pow(a[i],v);
for(int i=lid+1;i<rid;i++)
{
mul_tag[i]=Pow(mul_tag[i],v);
add_tag[i]=Pow(add_tag[i],v); // 不要忘了同时更新add_tag的值
}
spread(rid);
for(int i=r;id[i]==rid;i--)
a[i]=Pow(a[i],v);
}
-
单点查询
要先下传标记哦,否则结果会错误。
int ask(int x)
{
spread(id[x]);
return a[x];
}
Tips: 别忘了把 \(mul\_tag\) 的值都设为 \(1\)。
for(int i=1;i<=id[n];i++) // 用id[n],而不是len,有可能有1的误差
mul_tag[i]=1;
Example8: 数列分块入门8 LibreOJ #6284
给出一个长为 \(n\) 的数列,以及 \(n\) 个操作,
操作涉及区间询问等于一个数 \(c\) 的元素,并将这个区间的所有元素改为 \(c\)。
如果一个块中所有的元素都为同一个值,就不必再遍历每一个数了。
利用上述思想进行优化分块即可。
用 \(tag[i]\) 表示第 \(i\) 个块元素的值是否都一样,\(b[i]\) 表示第 \(i\) 块集体更改的值。
void spread(int x)
{
if(tag[x]) // 如果这个块元素的值都一样,将每个元素的值更新一下
{
int l=(x-1)*len+1,r=min(x*len,n);
for(int i=l;i<=r;i++)
a[i]=b[x];
}
}
int solve(int l,int r,int v)
{
int lid=id[l],rid=id[r],cnt=0;
if(lid==rid)
{
spread(lid); // 下传这个块的值
for(int i=l;i<=r;i++)
{
if(a[i]==v) cnt++; // 如果值为v,统计个数+1
else a[i]=v; // 否则将这个元素的值改为v
}
tag[lid]=false; // 这个块的元素值不同了,因为只有一部分元素的值进行多了更改
return cnt;
}
spread(lid);
for(int i=l;id[i]==lid;i++)
{
if(a[i]==v) cnt++;
else a[i]=v;
}
tag[lid]=false;
for(int i=lid+1;i<rid;i++)
{
if(tag[i]) // 如果这个块的元素值相同
{
if(b[i]==v) cnt+=sze[i]; // 如果这个块的值为v,答案加上这个块的长度
else b[i]=v; // 否则这个块的值改为v
}
else // 元素值不同只能进行暴力更改
{
int ll=(i-1)*len+1,rr=min(i*len,n);
for(int j=ll;j<=rr;j++)
if(a[j]==v) cnt++;
// 查询之后这个块的值就统一更改为v了,更新标记
tag[i]=true;
b[i]=v;
}
}
spread(rid);
for(int i=r;id[i]==rid;i--)
{
if(a[i]==v) cnt++;
else a[i]=v;
}
tag[rid]=false;
return cnt;
}
Tips: 用 数组 \(sze\) 表示每一个块的长度,调用更方便。
for(int i=1;i<=id[n];i++)
{
int l=(i-1)*len+1,r=min(i*len,n);
sze[i]=r-l+1; // 由于最后一个块不一定为整块,故不能直接等于块长len
}
Example9: 数列分块入门9 LibreOJ #6285
给出一个长为 \(n\) 的数列,以及 \(n\) 个操作,操作涉及询问区间的最小众数。
最后一道例题了,开心吗(o゚v゚)ノ(这是最难的一道例题了)
由于不会进行更改元素的值,我们可以预处理出每一块的区间众数,与分块思想照应。
这里我们用 pair<int,int>
来存储 数组 \(f\)。
\(f[i][j].first\) 表示 \(i\sim j\) 的块中,出现次数最多的的值,次数为多少。
\(f[i][j].second\) 表示 \(i\sim j\) 的块中,出现次数最多的值,最小为多少。(因为询问最小众数)
for(int i=1;i<=id[n];i++)
{
int max_cnt=0,min_val=0,cnt[N];
memset(cnt,0,sizeof cnt); // 记得清空cnt
int l=(i-1)*len+1;
for(int j=l;j<=n;j++) // 要一直枚举到n哦~
{
cnt[a[j]]++;
if(max_cnt<cnt[a[j]] || (max_cnt==cnt[a[j]]&&min_val>a[j]))
// 找到出现次数最多的,值最小的那个数
max_cnt=cnt[a[j]],min_val=a[j];
f[i][id[j]]={max_cnt,min_val};
}
}
因为本题元素值较大,不能作为数组下标,需要离散化。
scanf("%d",&n);
len=80; // len=sqrt(n) 会超时,不清楚为什么 >︿<
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
id[i]=(i-1)/len+1;
c[i]=a[i]; // 用c[i]进行离散化
}
// STL离散化
sort(c+1,c+1+n);
int cn=unique(c+1,c+1+n)-(c+1);
for(int i=1;i<=n;i++)
{
int t=lower_bound(c+1,c+1+cn,a[i])-(c+1);
// 在c中找到第一个大于等于a[i]的位置
// 由于c中元素值和a中是相同的,也就是找到离散化之后a[i]的位置
b[t]=a[i]; // b[a[i]]的值为没有离散化时a[i]的值
a[i]=t; // 离散化之后第i个数的位置,也就是离散化之后的值
vec[a[i]].push_back(i); // 用vec存值为a[i]元素的位置
}
之后进行分块处理就行了。
int solve(int l,int r)
{
int lid=id[l],rid=id[r];
// 直接统计整块的信息
int max_cnt=f[lid+1][rid-1].first;
int min_val=f[lid+1][rid-1].second;
if(lid==rid)
{
for(int i=l;i<=r;i++)
{
auto& t=vec[a[i]];
int cnt=upper_bound(t.begin(),t.end(),r)-lower_bound(t.begin(),t.end(),l);
// 找到>r的位置和>=l的位置,两者相减就是l~r中值为a[i]的个数
if(max_cnt<cnt || (max_cnt==cnt&&min_val>a[i]))
max_cnt=cnt,min_val=a[i];
}
return min_val;
}
for(int i=l;id[i]==lid;i++)
{
auto& t=vec[a[i]];
int cnt=upper_bound(t.begin(),t.end(),r)-lower_bound(t.begin(),t.end(),l);
if(max_cnt<cnt || (max_cnt==cnt&&min_val>a[i]))
max_cnt=cnt,min_val=a[i];
}
for(int i=r;id[i]==rid;i--)
{
auto& t=vec[a[i]];
int cnt=upper_bound(t.begin(),t.end(),r)-lower_bound(t.begin(),t.end(),l);
if(max_cnt<cnt || (max_cnt==cnt&&min_val>a[i]))
max_cnt=cnt,min_val=a[i];
}
return min_val;
}
在最后输出的时候,应输出原数值,而不是离散化之后的。
for(int i=1;i<=n;i++)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",b[solve(l,r)]);
}
Exercise1: 蒲公英 Luogu P4168 [Violet]
在乡下的小路旁种着许多蒲公英,而我们的问题正是与这些蒲公英有关。
为了简化起见,我们把所有的蒲公英看成一个长度为 \(n\) 的序列 \(\{a_1,a_2..a_n\}\),
其中 \(a_i\) 为一个正整数,表示第 \(i\) 棵蒲公英的种类编号。
而每次询问一个区间 \([l, r]\),你需要回答区间里出现次数最多的是哪种蒲公英,
如果有若干种蒲公英出现次数相同,则输出种类编号最小的那个。
注意,你的算法必须是在线的。
简化题意:和 Example9 一模一样。
在输出的时候根据输出要求进行在线操作即可。
int x=0;
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
l=(l+x-1)%n+1,r=(r+x-1)%n+1;
if(l>r) swap(l,r);
int ans=solve(l,r);
printf("%d\n",b[ans]);
x=b[ans];
}
Exercise2: 作诗 Luogu P4315
SHY 找来一篇长度为 \(n\) 的文章,阅读 \(m\) 次,
每次只阅读其中连续的一段 \([l,r]\),从这一段中选出一些汉字构成诗。
因为 SHY 喜欢对偶,所以 SHY 规定最后选出的每个汉字都必须在 \([l,r]\) 里出现了正偶数次。
而且 SHY 认为选出的汉字的种类数越多越好。
问题简述:
给定 \(n\) 个不大于 \(c\) 的正整数 \(a_1 \dots a_n\) 和 \(m\) 组询问,每次问 \([l,r]\) 中有多少个数出现正偶数次。
不难发现,和上题的题型非常相似,因此只是统计内容变了。
因此我们根据题意,更改一下 \(f\) 数组的含义即可。
\(sum[i][j]\) 表示前 \(i\) 个块中汉字为 \(j\) 的个数。
\(cnt[i][j]\) 表示 \(i\sim j\) 的块中,根据题意的结果为多少。
for(int i=2;i<=id[n];i++)
for(int j=1;j<=c;j++)
sum[i][j]+=sum[i-1][j];
for(int i=1;i<=id[n];i++)
{
int res=0,l=(i-1)*len+1;
for(int j=l;j<=n;j++)
{
cnt[a[j]]++;
if(cnt[a[j]]%2==0 && cnt[a[j]]) res++; // 为偶数,数量+1
else if(cnt[a[j]]>2) res--; // 由偶数又变成了奇数,数量-1
f[i][id[j]]=res;
}
// 清空cnt数组
for(int j=l;j<=n;j++)
cnt[a[j]]--;
}
之后和上题一样按照分块的思想进行处理即可。
int solve(int l,int r)
{
int lid=id[l],rid=id[r];
int res=f[lid+1][rid-1];
if(lid==rid)
{
for(int i=l;i<=r;i++)
{
cnt[a[i]]++;
if(cnt[a[i]]%2==0 && cnt[a[i]]) res++;
else if(cnt[a[i]]>2) res--;
}
for(int i=l;i<=r;i++)
cnt[a[i]]--;
return res;
}
for(int i=l;id[i]==lid;i++)
{
cnt[a[i]]++;
int t=cnt[a[i]]+sum[rid-1][a[i]]-sum[lid][a[i]];
// 记得加上 lid+1~rid-1 之间的块中相同汉字的数量
// 为了后续清空数组耗时短,不再累加到cnt数组中
if(t%2==0 && t) res++;
else if(t>2) res--;
}
for(int i=r;id[i]==rid;i--)
{
cnt[a[i]]++;
int t=cnt[a[i]]+sum[rid-1][a[i]]-sum[lid][a[i]];
if(t%2==0 && t) res++;
else if(t>2) res--;
}
for(int i=l;id[i]==lid;i++)
cnt[a[i]]--;
for(int i=r;id[i]==rid;i--)
cnt[a[i]]--;
return res;
}
二、一些想法
-
分块的各种操作不像树状数组或者线段树那样,基本操作的写法不变
它会根据查询内容的不同写法发生很大变化,同时
vector
似乎发挥了很大作用 -
还有一些题,先不写了,这些基本的板子题先写出来,然后去写莫队啦༼ つ ◕_◕ ༽つ
其他题有时间了再写,到时候再写下一个分块的博客吧
-
这篇博客只写了半天,和上篇单调队列相比,时间少了好多
可能是这篇是题都写完了才写的博客,上一个是一边学一边写
也可能是越写越快吧(o゜▽゜)o☆