Loading...

洛谷P3396 哈希冲突

check评论:0 条 remove_red_eye浏览量:408 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-11-02

这道题是一道挺有趣的分块题

给你一个数列,每次要么查询编号(从输入的$1$到$n$)对$x$取模为$j$的所有数字之和,要么修改一个数,数字最多$150000$个

然后就发现了平衡树,线段树啥的都不好维护这个玩意,考虑分块

首先发现如果从$1$枚举到$n$,时间复杂度最大是$n^2$

然后可以发现,当模数$x$增大时,单次暴力时间会越来越小

我们考虑将模数在$\sqrt n$以下的全部预处理,时间复杂度$O(n\sqrt n)$,模数大于$\sqrt n$的我们就暴力,单次时间复杂度$O(\sqrt n)$

那如何修改?

我们一样从$1$到$\sqrt n$的所有模数枚举,修改加值,单次时间复杂度$O(\sqrt n)$

所以总时间复杂度$O(n\sqrt n)$,可以很好的完成此题

#include <bits/stdc++.h>
using namespace std;
int f[400][400],a[150010],n,m;
int main()
{
    cin>>n>>m;
    int block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=block;i++)
    {
        for(int j=1;j<=n;j++)
        {
            f[i][j%i]+=a[j];
        }
    }
    char opt[5];
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%s%d%d",opt,&x,&y);
        if(opt[0]=='A')
        {
            if(x<=block)
            {
                printf("%d\n",f[x][y]);
            }
            else
            {
                int ans=0;
                for(int j=y;j<=n;j+=x)
                {
                    ans+=a[j];
                }
                printf("%d\n",ans);
            }
        }
        else
        {
            for(int j=1;j<=block;j++)
            {
                f[j][x%j]+=(y-a[x]);
            }
            a[x]=y;
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名