P3396 哈希冲突 (根号算法)
2020-12-13 05:58
标签:cti hash冲突 字符 word iostream open oid tps 技术 题目链接:https://www.luogu.org/problemnew/show/P3396 众所周知,模数的hash会产生冲突。例如,如果模的数 B君对hash冲突很感兴趣。他会给出一个正整数序列 自然,B君会把这些数据存进hash池。第 B君会给定许多个 另外,B君会随时更改 保证11=pn.题目描述
p=7
,那么4
和11
便冲突了。value[]
。value[k]
会被存进(k%p)
这个池。这样就能造成很多冲突。p
和x
,询问在模p
时,x
这个池内数的总和
。value[k]
。每次更改立即生效。
输入输出格式
输入格式:
第一行,两个正整数n,m
,其中n
代表序列长度,m
代表B君的操作次数。
第一行,n
个正整数,代表初始序列。
接下来m
行,首先是一个字符cmd
,然后是两个整数x,y
。
-
若
cmd=‘A‘
,则询问在模x
时,y
池内数的总和。 -
若
cmd=‘C‘
,则将value[x]
修改为y
。
输出格式:
对于每个询问输出一个正整数,进行回答。
输入输出样例
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
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.
对于60%
的数据,有n.
对于100%
的数据,有n.
保证所有数据合法,且1.
看了一下题,只会暴力,在分块专题里找的,疯狂找分块方案,还是不会QWQ,看大佬的题解,蒟蒻只能Orz,
这应该可以算是一个神奇的分块吧qwq,下面请看大佬的题解
这是一道论文题。集训队论文《根号算法——不只是分块》。
首先,题目要我们求的东西,就是下面的代码:
for(i=k;i
即:从 k开始,每隔p个数取一个数,求它们的和。
这个算法的复杂度是O(n^2)O(n2)的。
令答案为ans[p][k]ans[p][k],表示模数是p,余数是k.
那么,对于第i个数,如何处理它对ans的贡献呢?
for(p=1;p//枚举模数 ans[p][i%p]+=value[i]; //处理对应的贡献
这样看上去很妙的样子,然而O(n^2)O(n2)的预处理, O(1)O(1)询问,空间复杂度还是
O(n^2)O(n2)的
所以我们很自然地想到:只处理[1,\sqrt{n}][1,n?]以内的p
这样的话,令 size=\sqrt{n}size=n?,则可以这样预处理:
for(p=1;p//只枚举[1,size]中的 ans[p][i%p]+=value[] //处理对应的贡献
于是预处理的复杂度降到了 O(n\sqrt{n})O(nn?).
接着考虑询问。如果询问的p
如果p超过size,我们就暴力统计并回答。因为 p>\sqrt{n}p>n?,所以少于\sqrt{n}n?个数对答案有贡献。所以对于 p>\sqrt{n}p>n?,暴力统计的复杂度是 O(\sqrt{n})O(n?)..
接着考虑修改。显然我们把p
void change(int i,int v) //将value[i]改为v { for(p=1;p//更新答案 value[i]=v; //更新value数组 }
这样,我们就在O((m+n)\sqrt{n})O((m+n)n?).的时间内完成了任务
自己ac的代码
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ > < ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ #include#include using namespace std; #define ll long long const int maxn=150000+5; const int maxn1=1500+5; bool cmp(){ return 0; } int a[maxn]; int ans[maxn1][maxn1]; //set a,b; setint,int> > ps; set int,int> > pt; int n,q; void init(){ for(int i=1; ii) for(int p=1; p*pp) ans[p][i%p]+=a[i]; } void updata(int x, int val){ for(int p=1; p*pp){ ans[p][x%p]+=(val-a[x]); } a[x]=val; } int main(){ std::ios::sync_with_stdio (false); int flag=1; int x,y; cin>>n>>q; for(int i=1; i>a[i]; init(); while(q--){ string cmd; cin>>cmd>>x>>y; if(cmd=="A"){ if(x*x"\n"; else { int ret=0; for(int i=y; ia[i]; cout"\n"; } } else updata(x,y); } return 0; }
P3396 哈希冲突 (根号算法)
标签:cti hash冲突 字符 word iostream open oid tps 技术
原文地址:https://www.cnblogs.com/mrdushe/p/11160305.html
上一篇:win7IIS错误修改路径最全的