day 2 分块莫队入门

分块莫队入门

分块

把原数据分成几块，在每一块上进行预处理等措施，从而减少时间复杂度。

分块的大小可以通过均值不等式计算出最优值。

T1 P11221 [COTS 2019] 序列操作 K-ti

给定 \(a_0,...,a_{n-1},k\)，进行 \(n\) 次操作，每次删去序列第 \({0,k,2k,...}\) 项中的最大值，如果有多个最大，删去下标最小的，每次输出删除的数字，后面的数字向前补齐。

先不确定分块大小，设每 \(B\) 个分成一块。

设 \(f_{i,j}\) 为第 i 组，在组内的位置模 k 为 j 的最大值，先暴力预处理出这个数组。

每次删除时，考虑如何找到最大值，因为每次删除后，删除数字后的所以数字下标都会改变，所以我们用 \(s_i\) 表示前 i 组有多少的数每删掉，对于第 i 组，每次可以删掉的数就变为 \(f[i][k-s[i-1]\%k]\%k\)，每次删除枚举所有的块，复杂度 \(O(n/B)\)。

删除之后，这一块和这之后的所以块的 s 都要减少 1，复杂度为组数，\(O(n/B)\)。

因为这个数的删除，这一组中的 f 数组也发生了变化，我们需要重构 \(f[i]\)，首先把 \(f[i]\) 清空，再遍历一次块中的所有值进行更新，复杂度为块长 \(O(B)\)。

共有 n 次操作，总复杂度 \(O(N+N*(\frac{N}{B}+B)\)，由均值不等式，得 \(\frac{N}{B}=B\)，所以取 \(B=\sqrt{n}\)。

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[100005];
int f[505][100005];
int s[1005];
bool del[100005];
int main(){ios::sync_with_stdio(0);cin.tie();cin>>n>>k;int b=1000;for(int i=0;i<n;i++)cin>>a[i];memset(f,-1,sizeof f);for(int i=0;i<n;i++){int bl=i/b;int j=(i-bl*b)%k;if(f[bl][j]==-1||a[i]>a[f[bl][j]])f[bl][j]=i;s[bl]++;}for(int i=1;i<=(n-1)/b;i++)s[i]+=s[i-1];for(int t=0;t<n;t++){int p=-1;for(int i=0;i<=(n-1)/b;i++){int pre=(i==0?0:s[i-1]);int need=(k-pre%k)%k;if(f[i][need]!=-1&&(p==-1||a[f[i][need]]>a[p]))p=f[i][need];}cout<<a[p]<<"\n";del[p]=1;for(int i=p/b;i<=(n-1)/b;i++)s[i]--;int bl=p/b;memset(f[bl],-1,sizeof(int)*k);int cur=0;for(int i=bl*b;i<min(bl*b+b,n);i++){if(del[i])continue;int j=cur%k;if(f[bl][j]==-1||a[i]>a[f[bl][j]])f[bl][j]=i;cur++;}}return 0;
}

莫队

莫队适用于可以快速的从 \([l,r]\)，转移到 \([l,r+1]\) 等相邻区间的情况，且没有修改。

先把所有的询问按照 l 进行分块，然后按如下方法排序：

• 先按组进行从小到大排序
• 在同一组的数据，按 r 从小到大排序

然后我们按照排序后的顺序处理每个询问，发现在块里，l 最多总共移动 n 次，如果两次 l 跨了不同的块，每次最多移动 n 次，但这种情况出现的次数不会超过块数 \(n/B\)，所以最坏情况下是 \(N*\frac{N}{B}\)。

考虑右端点，在同一个块中，因为按 r 排序，所以最多移动 n 次，那么乘上块数就是 \(N*\frac{N}{B}\)。

如果扩展左右端点是 \(O(1)\) 的，那么最终复杂度就是 \(O(N*\frac{N}{B}+Q*B)\)。

常数优化：同一块中，奇数块按 r 从小到大排，偶数块按 r 从大到小排，可以减小 r 的移动次数。

T5 P1494 [国家集训队] 小 Z 的袜子

有 n 个袜子，给出他们的颜色，每次给出一个区间，从这里面随机拿两个袜子，求袜子颜色一样的概率，个数询问数量 \(N,M\le 50000\)。

最终概率极为拿到两个每种相同颜色概率之和除以总方案数：

\[\frac{\sum cnt_i(cnt_i-1)}{(r-l+1)(r-l)} \]

考虑用莫队维护 \(cnt_i\)。

在拓展端点的时候，例如右端点向右，要更新 \(cnt_i\)，把答案加上 \(cnt_i^2-(cnt_i-1)^2=2cnt_i-1\)，其他情况同理，见代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[50005];
struct ask{int x,y,id,id2;
}q[50005];
int cnt[50005];
struct frac{int x,y;
}now,ans[50005];
bool cmp(ask x,ask y){if(x.id==y.id)return x.y<y.y;return x.id<y.id;
}
bool cmp2(ask x,ask y){return x.id2<y.id2;
}
void add(int c){cnt[c]++;if(cnt[c]>1)now.x=now.x+(cnt[c]*(cnt[c]-1)-(cnt[c]-1)*(cnt[c]-2));
}
void del(int c){cnt[c]--;if(cnt[c]>0)now.x=now.x+(cnt[c]*(cnt[c]-1)-(cnt[c]+1)*cnt[c]);
}
signed main(){cin>>n>>m;int b=(int)sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){cin>>q[i].x>>q[i].y;q[i].id=(q[i].x-1)/b;q[i].id2=i;}sort(q+1,q+m+1,cmp);int l=q[1].x,r=q[1].y;for(int i=l;i<=r;i++)add(a[i]);now.y=(r-l+1)*(r-l);if(now.y==0) ans[q[1].id2]={0,1};else{int g=__gcd(now.x,now.y);ans[q[1].id2].x=now.x/g;ans[q[1].id2].y=now.y/g;}for(int i=2;i<=m;i++){while(l<q[i].x)del(a[l++]);while(l>q[i].x)add(a[--l]);while(r<q[i].y)add(a[++r]);while(r>q[i].y)del(a[r--]);now.y=(r-l+1)*(r-l);if(now.y==0) ans[q[i].id2]={0,1};else{int g=__gcd(now.x,now.y);ans[q[i].id2].x=now.x/g;ans[q[i].id2].y=now.y/g;}}for(int i=1;i<=m;i++){if(ans[i].x==0) cout<<"0/1\n";else cout<<ans[i].x<<"/"<<ans[i].y<<"\n";}return 0;
}

T11 P4168 [Violet] 蒲公英

一个长度为 n 的序列 a，m 次询问，每次询问求 \([l,r]\) 之间的众数。\(n,m\le 40000\)。

还是考虑每 B 个数分成一块，如何应对查询。

若查询区间的 l,r 分别在第 posl,posr 块，那么我们进行分类讨论：

• 当 \(posr-posl\le 1\) 时，这个时候区间很小，直接用一个桶暴力枚举，复杂度 \(O(\frac{n}{B})\)，注意每次清空时，枚举 l,r 直接的所有数，不要全部清空，否则复杂度错误，后面的情况同理。

• 当 \(posr-posl\ge 2\) 时，说明两个端点所在块的中间有其他块，现在的状态如图所示：|代表块的间隔，记 l 右边的块间隔为 x，r 左边的块间隔为 y。

  |  l___|______|...|______|___r  |x                 y
  

  我们需要快速计算中间的块，以达到优化的目的，现在考虑众数的两种出现方式：

  • 众数在 \([l,x]\) 或 \([y,r]\) 之间。我们可以预处理出前缀和 \(s[i][j]\) 表示前 i 个块中数字 j（所有数要先离散化）有多少个，把所有块暴力枚举即可求，复杂度 \(O(n\frac{n}{B})\)，这样我们就可以快速求出 \([x,y]\) 这些块的某一数字数量，所有我们枚举 \([l,x]\) 和 \([y,r]\) 之间的所有数，出现次数即为两端的次数加上中间的次数，枚举的复杂度为 \(O(n\frac{n}{B})\)。
  • 还有一种情况，就是 \([l,x]\) 和 \([y,r]\) 之间没有众数，那么众数只有一种可能，就是 \([x,y]\) 的众数，两种方案需要取 max，对于这种情况，可以预处理出 \(p[i][j]\) 表示第 i 块到第 j 块的众数，计算方式为暴力枚举所有的 \((i,j)\)，每次移动 j 时对桶更新新一块的所有数，预处理复杂度 \(O(n\frac{n}{B})\)，查询复杂度 \(O(1)\)。

加上离散化需要的排序复杂度，最终复杂度为 \(O(n\frac{n}{B}+n\log n\)。依据均值不等式，\(B=\sqrt{n}\) 时复杂度最优，为 \(O(n\sqrt{n}+n\log n)\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,l0,r0,l,r,x;
int a[40005];
struct node{int x,y;
}b[40005];
int c[40005];
int p[505][505],s[505][40005];
bool cmp(node x,node y){return x.x<y.x;
}
int cnt[40005];
signed main(){cin>>n>>m;int B=(int)sqrt(n);int g=(n+B-1)/B;for(int i=1;i<=n;i++){cin>>a[i];b[i].x=a[i];b[i].y=i;}sort(b+1,b+n+1,cmp);int t=0;b[0].x=-1;for(int i=1;i<=n;i++){if(b[i].x!=b[i-1].x)t++;c[t]=a[b[i].y];a[b[i].y]=t;}for(int i=1;i<=g;i++){memset(cnt,0,sizeof cnt);int maxcnt=0,maxn=0;for(int j=i;j<=g;j++){for(int k=(j-1)*B+1;k<=j*B;k++){cnt[a[k]]++;if(cnt[a[k]]>maxcnt||(cnt[a[k]]==maxcnt&&a[k]<maxn)){maxcnt=cnt[a[k]];maxn=a[k];}}p[i][j]=maxn;}}for(int i=1;i<=g;i++){for(int j=1;j<=t;j++)s[i][j]=s[i-1][j];for(int j=(i-1)*B+1;j<=i*B;j++)s[i][a[j]]++;}while(m--){cin>>l0>>r0;l=((l0+x-1)%n)+1;r=((r0+x-1)%n)+1;if(l>r)swap(l,r);int posl=(l+B-1)/B,posr=(r+B-1)/B;if(posr-posl<=1){for(int i=l;i<=r;i++)cnt[a[i]]=0;int maxcnt=0,maxn=0;for(int i=l;i<=r;i++){cnt[a[i]]++;if(cnt[a[i]]>maxcnt||(cnt[a[i]]==maxcnt&&a[i]<maxn)){maxcnt=cnt[a[i]];maxn=a[i];}}cout<<c[maxn]<<"\n";x=c[maxn];}else{int maxn = p[posl+1][posr-1];int maxcnt = s[posr-1][maxn] - s[posl][maxn];for(int i=l;i<=posl*B;i++)cnt[a[i]]=0;for(int i=(posr-1)*B+1;i<=r;i++)cnt[a[i]]=0;for(int i=l;i<=posl*B;i++)cnt[a[i]]++;for(int i=(posr-1)*B+1;i<=r;i++)cnt[a[i]]++;for(int i=l;i<=posl*B;i++){int x=cnt[a[i]]+s[posr-1][a[i]]-s[posl][a[i]];if(x>maxcnt||(x==maxcnt&&a[i]<maxn))maxcnt=x,maxn=a[i];}for(int i=(posr-1)*B+1;i<=r;i++){int x=cnt[a[i]]+s[posr-1][a[i]]-s[posl][a[i]];if(x>maxcnt||(x==maxcnt&&a[i]<maxn))maxcnt=x,maxn=a[i];}cout<<c[maxn]<<"\n";x=c[maxn];}}return 0;
}

T13 CF86D Powerful array

对于每一个正整数 \(s\)，记 \(K_s\) 为子数组中 \(s\) 出现的次数。我们定义该子数组的“幂”为对每个出现过的 \(s\) 计算 \(K_s \cdot K_s \cdot s\) 的和。

给定数组 a，你需要计算给定的 \(t\) 个子数组的“幂”。

\(1 \leq n, t \leq 200000\)，\(1 \leq a_i \leq 10^6\)

还是考虑扩充/缩小范围时答案的变化，注意到值域不大，所以我们用 \(cnt_i\) 记录 i 的出现次数，每加入一个数，在更新完 cnt 后答案的变化量为 \(cnt_i^2-(cnt_i-1)^2=2cnt_i-1\)，减小一个数同理，用莫队就做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,t,b;
int a[200005];
struct ask{int l,r,id,g,an;
}q[200005];
bool cmp(ask x,ask y){if(x.g==y.g)return x.r<y.r;return x.g<y.g;
}
bool cmp2(ask x,ask y){return x.id<y.id;
}
int cnt[1000005];
signed main(){cin>>n>>t; b=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=t;i++){cin>>q[i].l>>q[i].r;q[i].g=(q[i].l-1)/b;q[i].id=i;}sort(q+1,q+t+1,cmp);int ans=0;for(int i=q[1].l;i<=q[1].r;i++){cnt[a[i]]++;ans+=(cnt[a[i]]+(cnt[a[i]]-1))*a[i];}q[1].an=ans;int l=q[1].l,r=q[1].r;for(int i=2;i<=t;i++){while(l<q[i].l){ans-=(cnt[a[l]]+(cnt[a[l]]-1))*a[l];cnt[a[l]]--;l++;}while(l>q[i].l){l--;cnt[a[l]]++;ans+=(cnt[a[l]]+(cnt[a[l]]-1))*a[l];}while(r<q[i].r){r++;cnt[a[r]]++;ans+=(cnt[a[r]]+(cnt[a[r]]-1))*a[r];}while(r>q[i].r){ans-=(cnt[a[r]]+(cnt[a[r]]-1))*a[r];cnt[a[r]]--;r--;}q[i].an=ans;}sort(q+1,q+t+1,cmp2);for(int i=1;i<=t;i++)cout<<q[i].an<<"\n";return 0;
} 

T14 CF617E XOR and Favorite Number

有一个 \(k\)，以及一个长度为 \(n\) 的数组 \(a_{i}\)。回答 \(m\) 个询问，问你在区间 \(l \leq i \leq j \leq r\) 内，有多少组整数对 \((i,j)\)，使得数列 \(a_{i}, a_{i+1}, \ldots, a_{j}\) 的异或和等于 \(k\)。
\(1 \leq n, m \leq 100000\)，\(0 \leq k \leq 1000000\)，\(0 \leq a_{i} \leq 1000000\)

考虑新加入一个数，异或和等于 k 的会增加多少。

每次加入/删除后，计算前缀异或和为 \(k \text{ xor } a_i\) 的数量，就是产生/删除的异或区间的数量。

用莫队就做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
int a[200005];
int s[200005];
struct ask{int l,r,id,g,an;
}q[200005];
bool cmp(ask x,ask y){if(x.g==y.g)return x.r<y.r;return x.g<y.g;
}
bool cmp2(ask x,ask y){return x.id<y.id;
}
int cnt[10000005];
signed main(){cin>>n>>m>>k; int b=(int)sqrt(n);s[0]=0;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]^a[i];}for(int i=1;i<=m;i++){int L,R;cin>>L>>R;q[i].l=L-1;q[i].r=R;q[i].g=(q[i].l-1)/b;q[i].id=i;}sort(q+1,q+m+1,cmp);int ans=0;int l=0,r=-1;for(int i=1;i<=m;i++){while(l>q[i].l){l--;ans+=cnt[s[l]^k];cnt[s[l]]++;}while(l<q[i].l){cnt[s[l]]--;ans-=cnt[s[l]^k];l++;}while(r<q[i].r){r++;ans+=cnt[s[r]^k];cnt[s[r]]++;}while(r>q[i].r){cnt[s[r]]--;ans-=cnt[s[r]^k];r--;}q[i].an=ans;}sort(q+1,q+m+1,cmp2);for(int i=1;i<=m;i++)cout<<q[i].an<<"\n";return 0;
}