Luogu 3396 权值分块

时间：2023-03-09 15:12:54
Luogu 3396 权值分块

官方题解:这是一道论文题。集训队论文《根号算法——不只是分块》。

首先，题目要我们求的东西，就是下面的代码：

for(i=k;i<=n;i+=p)

    ans+=value[i];

即：从 k开始，每隔p个数取一个数，求它们的和。

这个算法的复杂度是Luogu 3396 权值分块的。

令答案为Luogu 3396 权值分块，表示模数是p，余数是k.

那么，对于第i个数，如何处理它对ans的贡献呢？

for(p=1;p<=n;p++) //枚举模数

    ans[p][i%p]+=value[i]; //处理对应的贡献

这样看上去很妙的样子，然而Luogu 3396 权值分块的预处理， Luogu 3396 权值分块询问，空间复杂度还是

Luogu 3396 权值分块的

所以我们很自然地想到：只处理Luogu 3396 权值分块以内的p

这样的话，令 Luogu 3396 权值分块，则可以这样预处理：

for(p=1;p<=size;p++) //只枚举[1,size]中的

    ans[p][i%p]+=value[] //处理对应的贡献

于是预处理的复杂度降到了 Luogu 3396 权值分块.

接着考虑询问。如果询问的p<size ，那显然可以Luogu 3396 权值分块给出回答。

如果p超过size，我们就暴力统计并回答。因为 Luogu 3396 权值分块，所以少于Luogu 3396 权值分块个数对答案有贡献。所以对于 Luogu 3396 权值分块，暴力统计的复杂度是 Luogu 3396 权值分块..

接着考虑修改。显然我们把p<size的值全都更新一遍就行。复杂度也是 Luogu 3396 权值分块.

void change(int i,int v) //将value[i]改为v

    {

    for(p=1;p<=size;p++)

    ans[p][i%p]=ans[p][i%p]-value[i]+v; //更新答案

    value[i]=v; //更新value数组

}

这样，我们就在Luogu 3396 权值分块.的时间内完成了任务

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 const int Maxn=;

 const int Sqrt=;

 int n,m,Block,a[Sqrt][Sqrt],x,y,v[Maxn];

 int main()

 {

     scanf("%d%d",&n,&m); Block=(int)sqrt(n);

     for (int i=;i<=n;i++) scanf("%d",&v[i]);

     memset(a,,sizeof(a));

     for (int i=;i<=Block;i++)

         for (int j=;j<=n;j++) a[i][j%i]+=v[j];

     for (int i=;i<=m;i++)

     {

         char ch=getchar();

         while (ch!='A' && ch!='C') ch=getchar();

         scanf("%d%d",&x,&y);

         if (ch=='A')

         {

             if (x<=Block) printf("%d\n",a[x][y]); else

             {

                 int Ret=; for (int i=y;i<=n;i+=x) Ret+=v[i]; printf("%d\n",Ret);

             }

         }

         if (ch=='C')

         {

             for (int i=;i<=Block;i++)

                 a[i][x%i]=a[i][x%i]-v[x]+y;

             v[x]=y;

         }

     }

     return ;

 }

C++

其实这道题因为数据弱暴力都能过

相关文章