题目概述

Luogu5309

解题报告

题目保证 $y\le x$ ，因此每次都是全局 $i\bmod x=y$ 的 $a_i$ 加上 $z$ 。

不难想到 $x>\sqrt n$ 时，我们直接暴力更新复杂度是 $O(\sqrt n)$ 的，而如果 $x\le \sqrt n$ ，我们记录 $val_{x,y}$ 表示 $x,y$ 这个操作的权值和。为了下面的操作，再记录 $sum_{x,y}=\sum_{i=0}^{y}val_{x,i}$（实际只需要维护 $sum_{x,y}$ ，也是 $O(\sqrt n)$ 暴力维护）。

询问 $[L,R]$ 时，对于 $x>\sqrt n$ 的部分直接统计 $\sum_{i=L}^{R}a_i$ ，然后考虑 $x\le\sqrt n$ 的部分，对于 $x,y$ 操作，我们把区间分为三部分：

• $L$ 到 $L$ 后面第一个$\bmod x=x-1$ 的部分：利用 $sum_{x,x-1}-sum_{x,L\bmod x-1}$ 计算
• $R$ 前面第一个$\bmod x=0$ 的部分到 $R$ ：利用 $sum_{x,R\bmod x}$ 的计算
• $L$ 到 $R$ 中间整块的部分：利用块数乘上 $sum_{x,x-1}$ 计算

为了让暴力更新 $a_i$ 的复杂度为 $O(1)$ ，我们不能使用树状数组之类的来维护 $a$ 的前缀和，因此考虑把 $a$ 数组也分块，这样暴力更新 $a_i$ 时同时更新 $a_i$ 和 $i$ 所在的块，然后查询时 $O(\sqrt n)$ 查询 $\sum_{i=L}^{R}a_i$ 。

总复杂度 $O(m\sqrt n)$ ，需要卡常。我们可以在查询中途不取模，最后再取模，不过这样在极限数据下（ $2e5\times2e5\times1e9=4e19$ ）会爆unsigned long long，但是我们发现这只有在 $x$ 全为 $1$ 的情况下出现，因此我们如果对 $x\le 2$ 的部分取模，其他不取模，那么极限数据就是 $2e5\times{2e5\over 3}\times 1e9=1.33e19$ 没有爆unsigned long long。

做了ynoi我也化身毒瘤！

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef unsigned long long ULL;
const int maxn=200000,S=448,MOD=1e9+7;

int n,m;
ULL a[maxn+5],sum[S+5],pre[S+5][S+5],ans;

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
struct fastO{
    int si;char buf[100000];
    fastO() {si=0;}
    inline void putc(char ch){
        if (si==100000) fwrite(buf,1,si,stdout),si=0;
        buf[si++]=ch;
    }
    ~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
    static int len=0,buf[100];
    if (x<0) putchar('-'),x=-x;
    do buf[len++]=x%10,x/=10; while (x);
    while (len) fo.putc(buf[--len]+48);
    fo.putc(ch);
}
#define BLK(i) (((i)-1)/S+1)
int main(){
    readi(n);readi(m);
    for (int i=1;i<=n;i++) readi(a[i]),sum[BLK(i)]+=a[i];
    for (int t=1,tp,x,y,z;t<=m;t++){
        readi(tp);readi(x);readi(y);
        if (tp==1){
            readi(z);
            if (x>S) for (int i=y;i<=n;i+=x) a[i]+=z,sum[BLK(i)]+=z;
            else for (int i=y%x;i<x;i++) pre[x][i]+=z;
        } else {
            ans=0;
            int l=BLK(x),r=BLK(y);
            if (l==r) {for (int i=x;i<=y;i++) ans+=a[i];} else {
                for (int i=x,lim=l*S;i<=lim;i++) ans+=a[i];
                for (int i=(r-1)*S+1;i<=y;i++) ans+=a[i];
                l++;r--;
                for (int i=l;i<=r;i++) ans+=sum[i];
            }
            for (int i=1;i<=S;i++)
                if (pre[i][i-1]){
                    int a=x%i,b=y%i,len=(y-b)-(x+i-a);
                    int tot=(len>0?len/i:0);
                    if (i<=2) ans+=pre[i][i-1]%MOD*tot%MOD;
                    else ans+=pre[i][i-1]*tot;
                    ans+=pre[i][b]-(a?pre[i][a-1]:0);
                    if (len>=0) ans+=pre[i][i-1];
                }
            writei(ans%MOD);
        }
    }
    return 0;
}