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

作者: wjyyy 分类: 分块,数据结构,解题报告 发布时间: 2018-09-23 16:43

点击量:16

 

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

 

题目描述

众所周知,模数的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;
}

说点什么

avatar
  Subscribe  
提醒
/* */