初次接触分块思想

初次接触分块思想

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

codeforces 86 D. Powerful array

​​    的和，其中Ks是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 #include #include #include #include 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>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

这是那道和mobius相关的题：

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

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

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

莫比乌斯反演：

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

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

#include #include 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>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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。