题目概述

CF GYM102309E

解题报告

这是队友提供的神仙解法，给了我一种全新的分块思路👍。

对于 $x$ ，令 $C_i=\overline{xx\cdots x}$（ $i$ 个 $x$ ），首先我们先考虑 $A_n$ 表示 $\sum_{i=1}^{n}C_i$ ，那么：$A_n=10A_{n-1}+xn$ 。

待定系数法，假设 $A_n+an+b=10[A_{n-1}+a(n-1)+b]$ ，得到 $a={x\over 9},b={10x\over 81}$ ，所以：

$$ A_n+{x\over 9}n+{10x\over 81}=10[A_{n-1}+{x\over 9}(n-1)+{10x\over 81}] $$

令 $B_n=A_n+{x\over 9}n+{10x\over 81}$ ，则 $B_1={100x\over 81},B_n=10^{n+1}{x\over 81}$ ，所以：

$$ A_n=x({10^{n+1}\over 81}-{n\over 9}-{10\over 81}) $$

得到了前缀和的通项公式之后，我们开始考虑做法。我们不难发现，如果使用线段树，标记是无法合并的，因此无法使用。同理，分块也无法进行标记的合并，但是，如果我们将标记都记在每块的第一个位置：

• $S_0$ ：加在第一个位置的 $C_i$ 的和
• $S_1$ ：加在第一个位置的 $x$ 的和

那么，如果想得知标记对第二个位置的贡献，只需要：$10S_0+S_1$ ，第三个位置同理 $10(10S_0+S_1)+S_1$ 。

也就是说，我们可以从每块的第一个位置开始，算出标记对后面位置的贡献，这样每次询问就可以 $O(\sqrt n)$ 算出不在整块里的元素的值！

然后我们再记录：

• $S_2$ ：块中所有元素的和
• $num_0$ ：整块被覆盖的次数
• $num_1$ ：块中所有元素覆盖次数的和

对于每次区间添加，给整块的 $S_0,S_1$ 加上第一个位置的贡献，然后给 $S_2$ 加上 $C_i$ 的一段区间和（用 $A_n$ ）。对于不在整块中的元素，则加上对应的 $C_i$ 即可。

不要忘记整块对单个元素的次数贡献，以及单个元素对整块的贡献。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=10000,maxb=100,MOD=1e9+7;
const int INV1=111111112,INV2=123456791;

int n,te,sum[maxn+5],cnt[maxn+5],c,pc;
int S[maxb+5][3],num[maxb+5][2],pw[maxn+5];

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int Pow(int w,int b) {int s=1;while (b) {if (b&1) s=MUL(s,w);w=MUL(w,w);b>>=1;}return s;}
int A(int n,int x){
    int a=MUL(MUL(pc,pw[n+1]),INV2),b=MUL(n,INV1),c=MUL(10,INV2);
    return ((LL)a+MOD-b+MOD-c)*x%MOD;
}
#define C(n,x) (ADD(A(n,x),MOD-A((n)-1,x)))
int main(){
    pw[0]=1;for (int i=1;i<=maxn+1;i++) pw[i]=(LL)pw[i-1]*10%MOD;
    while (~scanf("%d",&n)){
        for (int i=0;i<n;i++) sum[i]=cnt[i]=0;
        for (int i=0;i<=(n-1)/100;i++)
            S[i][0]=S[i][1]=S[i][2]=num[i][0]=num[i][1]=0;
        for (scanf("%d",&te);te;te--){
            int tp,L,R;scanf("%d%d%d",&tp,&L,&R);L--;R--;
            if (tp==1){
                int x;scanf("%d%d",&x,&c);pc=Pow(10,c);
                int l=L/100,r=R/100;
                if (l==r){
                    int X=C(1,x);
                    for (int i=L;i<=R;i++){
                        sum[i]=ADD(sum[i],X);cnt[i]++;
                        S[l][2]=ADD(S[l][2],X);num[l][1]++;
                        X=((LL)X*10+x)%MOD;
                    }
                } else {
                    l++;r--;
                    int X=C(1,x);
                    for (int i=L;i<l*100;i++){
                        sum[i]=ADD(sum[i],X);cnt[i]++;
                        S[l-1][2]=ADD(S[l-1][2],X);num[l-1][1]++;
                        X=((LL)X*10+x)%MOD;
                    }
                    for (int i=l;i<=r;i++){
                        S[i][0]=ADD(S[i][0],C(i*100-L+1,x));
                        S[i][1]=ADD(S[i][1],x);
                        S[i][2]=ADD(S[i][2],ADD(A((i+1)*100-L,x),MOD-A(i*100-L,x)));
                        num[i][0]=ADD(num[i][0],1);
                    }
                    X=C((r+1)*100-L+1,x);
                    for (int i=(r+1)*100;i<=R;i++){
                        sum[i]=ADD(sum[i],X);cnt[i]++;
                        S[r+1][2]=ADD(S[r+1][2],X);num[r+1][1]++;
                        X=((LL)X*10+x)%MOD;
                    }
                }
            } else {
                int l=L/100,r=R/100,SUM=0,NUM=0;
                if (l==r){
                    int pre=S[l][0];
                    for (int i=l*100+1;i<=L;i++)
                        pre=((LL)pre*10+S[l][1])%MOD;
                    for (int i=L;i<=R;i++){
                        SUM=ADD(SUM,sum[i]);
                        SUM=ADD(SUM,pre);
                        NUM=ADD(NUM,cnt[i]);
                        NUM=ADD(NUM,num[l][0]);
                        pre=((LL)pre*10+S[l][1])%MOD;
                    }
                } else {
                    l++;r--;
                    int pre=S[l-1][0];
                    for (int i=(l-1)*100+1;i<=L;i++)
                        pre=((LL)pre*10+S[l-1][1])%MOD;
                    for (int i=L;i<l*100;i++){
                        SUM=ADD(SUM,sum[i]);
                        SUM=ADD(SUM,pre);
                        NUM=ADD(NUM,cnt[i]);
                        NUM=ADD(NUM,num[l-1][0]);
                        pre=((LL)pre*10+S[l-1][1])%MOD;
                    }
                    for (int i=l;i<=r;i++){
                        SUM=ADD(SUM,S[i][2]);
                        NUM=ADD(NUM,MUL(num[i][0],100));
                        NUM=ADD(NUM,num[i][1]);
                    }
                    pre=S[r+1][0];
                    for (int i=(r+1)*100;i<=R;i++){
                        SUM=ADD(SUM,sum[i]);
                        SUM=ADD(SUM,pre);
                        NUM=ADD(NUM,cnt[i]);
                        NUM=ADD(NUM,num[r+1][0]);
                        pre=((LL)pre*10+S[r+1][1])%MOD;
                    }
                }
                !NUM?puts("0"):printf("%lld\n",MUL(SUM,Pow(NUM,MOD-2)));
            }
        }
    }
    return 0;
}