CF1207F 根号分治

Link

CF1207F. Remainder Problem

题意

给你一个包含 $n$ 个数的数组，一开始每一位上都是 $0$。$q$ 次操作，第一个操作是单点修改，第二个操作是对于所有满足 $i$ % $y=x$ 的 $a_{i}$ 求和。

$n=500000$ $q<=500000$

题解

打CF时看清神秒了这题我还以为是数据结构，，，结果想了半天也想不出咋维护，，，

一种暴力的做法是对于每一个对 $y$ 和 $x$ 都开一个数组记录一下，但单点更新 $O(n)$，查询时 $O(1)$。

另一个种暴力做法就是直接求 $a_{x}+a_{x+y}+a_{x+2y}+a_{x+3y}…$ 最差情况下也是 $O(n)$ 的，更新时 $O(1)$。

当 $n$ 很小的时候第一种暴力很有效，当 $n$ 很大时第二种暴力也很会快，因此我们考虑定一个上界 $m$，对于小于 $m$ 的 $x$ 我们选择第一种暴力方式，大于 $m$ 我们用第二种暴力。

这样单次询问或查询的复杂度是$O(m+n/(n-m))$的，显然 $m$ 取 $sqrt{n}$ 时复杂度最优。

这东西就是根号分治 真是太暴力了

Code

const int sqrtn=sqrt(MAXN);
 
int n=5e5,q;
LL s[sqrtn+5][sqrtn+5];
LL a[MAXN];
 
 
int work()
{
    q=read();
    while(q--)
    {
        int t=read(),x=read(),y=read();
        if(t==1){a[x]+=y;fp(i,1,sqrtn)s[i][x%i]+=y;}
        else
        {
            LL ans=0;
            if(x>sqrtn){for(int i=y;i<=n;i+=x)ans+=a[i];}
            else ans=s[x][y];
            write(ans),putchar('\n');
        }
    }
    return 0;
}