本文主要是介绍初次接触分块思想，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
在练习mobius反演的时候有一题需要用分块的思想来优化，于是第一次听说了分块思想。比较有名的当属号称可以解决所有不修改、离线查询问题的莫队算法。几乎所有的莫队算法的介绍都和[BZOJ]2038 小Z的袜子有关，相关大神博客：http://www.cnblogs.com/kuangbin/p/3263483.html先来个稍简单的分块题：
codeforces 86 D. Powerful array
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相关的题：
#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;
}
这篇关于初次接触分块思想的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
