洛谷 P3396 哈希冲突 题解【分块】

点击量：149

    一道用类似分块的算法优化复杂度的题。

目录

题目描述

众所周知，模数的hash会产生冲突。例如，如果模的数p=7，那么4和11便冲突了。

B君对hash冲突很感兴趣。他会给出一个正整数序列value[]。

自然，B君会把这些数据存进hash池。第value[k]会被存进(k%p)这个池。这样就能造成很多冲突。

B君会给定许多个p和x，询问在模p时，x这个池内数的总和。

另外，B君会随时更改value[k]。每次更改立即生效。

保证\(1\le p< n\).

 

输入输出格式

输入格式：

第一行，两个正整数n,m，其中n代表序列长度，m代表B君的操作次数。

第一行，n个正整数，代表初始序列。

接下来m行，首先是一个字符cmd，然后是两个整数x,y。

• 若cmd=’A’，则询问在模x时，y池内数的总和。

• 若cmd=’C’，则将value[x]修改为y。

输出格式：

对于每个询问输出一个正整数，进行回答。

输入输出样例

输入样例#1：

10 5
1 2 3 4 5 6 7 8 9 10
A 2 1
C 1 20
A 3 1
C 5 1
A 5 0

输出样例#1：

25
41
11

说明

样例解释

A 2 1的答案是1+3+5+7+9=25.

A 3 1的答案是20+4+7+10=41.

A 5 0的答案是1+10=11.

数据规模

对于\(10\%\)的数据，有\(n\le 1000,m\le 1000\).

对于\(60\%\)的数据，有\(n\le 100000.m\le 100000\).

对于\(100\%\)的数据，有\(n\le 150000,m<=150000\).

保证所有数据合法，且\(1\le value[i]\le 1000\).

题解：

    一开始感觉方向找对了，就是感觉小的可以预处理出来。发现复杂度降低并不明显，考虑预处理到\(100\)以内，预处理的复杂度还是可以的，分析数据范围后发现总复杂度达到了两亿左右，貌似可以水。不过看了题解发现就是分块，最大可以达到\(O(n\sqrt{n})\)，也就是五千万左右。

    对于\(150000\)的数据\(O(\sqrt{n})\)大概是\(370\)，因此预处理出每个数\(i\mod p,p\in [1,370]\)所映射的值，把这个值的\(sum\)加上\(value[i]\)即可。因为每次询问\(p\le \sqrt{n}\)的池中，暴力复杂度是大于\(\sqrt{n}\)的，而当\(p>\sqrt{n}\)时，暴力复杂度是小于\(\sqrt{n}\)的。那么当询问的\(p\le \sqrt{n}\)时，就输出预处理出的答案，否则暴力处理。

    这个题还有修改操作，好在是单点修改（区间修改还不会……），这样还是用\(\sqrt{n}\)的时间对\(p\le \sqrt{n}\)的模数池加上\(value’-value\)的差值，同时不要忘了改自己的\(value\)了。

    算是一个分块思想的题目吧，好像是基本不等式？？？\(a+b\ge 2\sqrt{ab}\)？？？时间复杂度\(O(n\sqrt{n})\)，有一定的常数。

Code：

#include<cstdio>
#include<cstring>
long long conf[500][500];
int a[150010];
int main()
{
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        for(int j=1;j<=400;++j)
            conf[j][i%j]+=a[i];
    }
    char op[10];
    long long sum=0;
    for(int i=1;i<=m;++i)
    {
        scanf("%s",op);
        scanf("%d%d",&u,&v);
        if(op[0]=='A')
        {
            if(u<=400)
                printf("%lld\n",conf[u][v]);
            else
            {
                sum=0;
                for(int j=v;j<=n;j+=u)
                    sum+=a[j];
                printf("%lld\n",sum);
            }
        }
        else
        {
            int delta=v-a[u];
            a[u]=v;
            for(int j=1;j<=400;++j)
                conf[j][u%j]+=delta;
        }
    }
    return 0;
}