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;
}