P5309 [Ynoi2011] 初始化 题解

昨天在机房弄了一个根号分治的小讲座，似乎还行。

但是同学反映这题和 [Ynoi2077] stdmxeypz 不是很懂，考虑那题我写了一个比较易懂的题解，所以我来写一个初始化的题解来供大家参考。

其实主要是讲题的时候这题讲得不是很明白，甚至有许多错误。

首先我更正一点，讲座的时候我很唐地看错题了，这题就是整体修改操作，不是区间修改操作。

因此我整个题应该都是讲错的，可能把大家都绕晕了。

然后考虑怎么维护。

首先 $x\geq \sqrt n$ 是容易的，直接单点修改记录在分块中即可。

然后考虑 $x\leq \sqrt n$ 也是容易想的，考虑维护 $\mod p$ 之后等于 $k$ 的标记的总和。

统计的时候首先要统计 $x\geq \sqrt n$ 的分块，然后对于每一种 $x\leq \sqrt n$ 都要单独统计。

考虑每个长度为 $x$ 的部分包含的标记都是一样的，所以我们处理散块，然后看整块的数量即可。

然后暴力处理散块是 $\mathcal O(\sqrt n)$ 的，整体来看单次查询操作时间复杂度会变成 $\mathcal O(n)$，考虑快速统计散块，发现就是快速统计前后缀，维护每个块的前缀和即可。

对于这道题目，复杂的地方主要是区间和操作

马蜂丑陋，很久之前的马蜂了。

我对我在讲座时犯下的低级错误向机房的所有同学致歉。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=2e5+5;
const LL M=3005;
const LL mod=1e9+7;
int n,m,B,op,x,y,used[M];
LL b[M],a[N],c[M][M],sum[M][M],z;
inline int read() 
{
    char c = getchar();
    int sum = 0,f=1;
    while ((c!='-')&&(c < '0' || c > '9')) c = getchar();
    if(c=='-')f=-1,c=getchar();
    do 
    {
        sum = (sum << 3) + (sum << 1) + c - '0';
        c = getchar();
    } while (c >= '0' && c <= '9');
    return sum*f;
}
inline int gtblock(int x,int k)
{
    return (x-1)/k+1;
}
inline int  L(int x,int k)
{
    return (x-1)*k+1;
}
inline int R(int x,int k)
{
    return x*k;
}
inline  void updone(int x,int y)
{
    a[x]=(a[x]+y);
    b[gtblock(x,B)]=(b[gtblock(x,B)]+y);
}
inline LL queryb(LL x,LL y)
{
    int xb=gtblock(x,B),yb=gtblock(y,B);
    LL  ans=0;
    if(xb==yb)
    {
        for(int i=x;i<=y;i++)
        {
            ans=ans+a[i];
        }
        return ans;
    }
    if(L(xb,B)!=x)
    {
        for(int i=x;i<=R(xb,B);i++)ans=(ans+a[i]);
        xb++;
    }
    if(R(yb,B)!=y)
    {
        for(int i=L(yb,B);i<=y;i++)ans=(ans+a[i]);
        yb--;
    }
    for(int i=xb;i<=yb;i++)
    {
        ans=(ans+b[i]);
    }
    return ans;
}

inline LL query(int x,int y,int k)
{
    if(used[k]==0)return 0;
    int xb=gtblock(x,k),yb=gtblock(y,k);
    LL ans=0;
    if(xb==yb)
    {
        for(int i=x;i<=y;i++)
        {
            ans=(ans+c[k][i%k]);
        }
        return ans;
    }

    if(L(xb,k)!=x)
    {
        int l=x%k,r=k;
        if(l==0)l=k;
        ans=(ans+sum[k][r]-sum[k][l-1]);
        xb++;
    }
    if(R(yb,k)!=y)
    {
        int l=1,r=y%k;
        ans=(ans+sum[k][r]-sum[k][l-1]);
        yb--;
    }
    ans=(ans+((LL)(yb-xb+1))*sum[k][k]);
    return ans;
}
int main()
{
    n=read(),m=read();
    B=max((int)(sqrt(n)/2),1);
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        b[gtblock(i,B)]=(b[gtblock(i,B)]+a[i]);
    }
    while(m--)
    {
        op=read();
        if(op==1)
        {
            x=read(),y=read(),z=read();
            if(x>B)
            {
                for(int i=y;i<=n;i+=x)updone(i,z);
            }
            else
            {
                c[x][y%x]=(c[x][y%x]+z);
                used[x]=1;
                for(int i=y;i<=x;i++)
                {
                    sum[x][i]=(sum[x][i]+z);
                }
            }
        }
        else
        {
            x=read(),y=read();
            LL ans=queryb(x,y);
            for(int i=1;i<=B;i++)
            {
                ans=(ans+query(x,y,i));
            }
            printf("%lld\n",(ans+mod)%mod);
        }
    }
}