初次接触分块思想

本文主要是介绍初次接触分块思想，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在练习mobius反演的时候有一题需要用分块的思想来优化，于是第一次听说了分块思想。比较有名的当属号称可以解决所有不修改、离线查询问题的莫队算法。几乎所有的莫队算法的介绍都和[BZOJ]2038 小Z的袜子有关，相关大神博客：http://www.cnblogs.com/kuangbin/p/3263483.html
先来个稍简单的分块题：

codeforces 86 D. Powerful array

http://codeforces.com/problemset/problem/86/D

大意：给定一串数字，给定一系列询问，问在相应区间内 K_s·K_s·s 的和，其中K_s是K数字S在区间内出现的次数。

分块解决，相关证明：

Let's sort the query intervals according to the following rule: first come the intervals with the left ends in Q_1, then the intervals with the left ends in Q_2, and so on. And if the left ends of the two queries belong to the same part, then the interval with the more left right end is assumed to be smaller.
In order to prove the stated asymptotic behavior we will follow the steps of the left and the right ends independently. We note that the left ends that belong to the same Q_i make <= n / p steps, and transition to Q_{i+1} costs no more than 2 * n / p steps. Therefore the left ends make <= n/p * n + 2*n steps (the second summand is O(n), and it's negligible).
The right ends in the common group move only to the right, and this proves <= n * p steps (during the whole process) estimate. We will estimate the transition to the next Q_i at no more than n steps, so overall we get < = 2 * n * p steps.
Thus, the total number of steps is no more than (n / p * n + 2 * n * p). Now we choose p = sqrt(n) which proves the statement.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=2e5+10,M=1e6+10;
int a[N],cnt[M];
struct node{int x,y,l,dex;
}edge[N];
int cmp(node a,node b){return a.l<b.l||(a.l==b.l&&a.y<b.y) ;
}
LL ans,res[N];
int L,R;
void query(int x,int y,int dex){if(dex){for(int i=L;i<x;i++){cnt[a[i]]--;ans=ans-((cnt[a[i]]<<1)+1)*a[i];}for(int i=x;i<L;i++){ans=ans+((cnt[a[i]]<<1)+1)*a[i];cnt[a[i]]++;}for(int i=R+1;i<=y;i++){ans=ans+((cnt[a[i]]<<1)+1)*a[i];cnt[a[i]]++;}for(int i=y+1;i<=R;i++){cnt[a[i]]--;ans=ans-((cnt[a[i]]<<1)+1)*a[i];}}else {for(int i=x;i<=y;i++) {ans=ans+((cnt[a[i]]<<1)+1)*a[i];cnt[a[i]]++;}}L=x;  R=y;
}
int main()
{//freopen("cin.txt","r",stdin);int n,t;while(cin>>n>>t){int len=sqrt(1.0*n);memset(cnt,0,sizeof(cnt));for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=0;i<t;i++){scanf("%d%d",&edge[i].x,&edge[i].y);edge[i].dex=i;edge[i].l=(edge[i].x-1)/len;}sort(edge,edge+t,cmp);ans=0;for(int i=0;i<t;i++){query(edge[i].x,edge[i].y,i);res[edge[i].dex]=ans;}for(int i=0;i<t;i++){printf("%I64d\n",res[i]);}}return 0;
}

这是那道和mobius相关的题：

spoj PGCD - Primes in GCD Table（mobius+分块)

http://www.spoj.com/problems/PGCD/en/

大意: 在一张(a,b)的表格中，填写完整对应交点值gcd(i,j)。问填写了多少次的素数。

即求解最大公约数是素数的组合有多少个。

莫比乌斯反演：

$\\F(n)=\sum\limits_{d|n}f(d)$

$\\f(d)=\sum\limits_{d|n}\mu(\frac{n}{d})F(n)$

其中d就是各种素数。求解

$\\f(d)=\sum\limits_{d|n}\mu(\frac{n}{d})F(n)\\=F(n)\sum\limits_{d|n}\mu(\frac{n}{d})$

学习了大神的博文： http://blog.csdn.net/jayye1994/article/details/12621589

设 $\\sum(n)=\mu(\frac{n}{k_1})+\mu(\frac{n}{k_2})+\cdots+\mu(\frac{n}{k_n})$

那么最开始处理时，sum[i*pri[j]]+=sum[i]; 再前缀和处理.

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N=1e7+10;
int mu[N],pri[N/10],cnt=0;
bool vis[N];
LL sum[N];
void getmu(){mu[1]=1;for(int i=2;i<N;i++){if(!vis[i]){mu[i]=-1;pri[cnt++]=i;}for(int j=0;j<cnt&&pri[j]*i<N;j++){vis[i*pri[j]]=1;if(i%pri[j]==0){mu[i*pri[j]]=0;break;}else mu[i*pri[j]]=-mu[i];}}for(int i=1;i<N;i++){if(mu[i]){for(int j=0;i*pri[j]<N&&j<cnt;j++){sum[i*pri[j]]+=mu[i];}}}for(int i=1;i<N;i++){sum[i]+=sum[i-1]*1LL;}
}
int main()
{//freopen("cin.txt","r",stdin);int a,b,t;getmu();cin>>t;while(t--){scanf("%d%d",&a,&b);if(a>b){a=a^b;  b=a^b;  a=a^b;}LL ans=0;for(int i=1;i<=a;i++){  //10/4=2;  10/2=5;int t1=a/i,t2=b/i;int next=min(a/t1,b/t2);ans=ans+1LL*t1*t2*(sum[next]-sum[i-1]);i=next;}printf("%lld\n",ans);}return 0;
}

这篇关于初次接触分块思想的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！