[NOIPシミュレーション2015.10.06]C

テーマの大意
Sは、十進法で4と7のみからなる全正の整数の集合として定義される.数列{an}が与えられ、次の2つの操作をサポートする必要があります.∙add(l,r,x):すべてのai(l≦i≦r)にx∙count(l,r):求め|{i|l≦i≦r,ai∈S}|を加える
1≦n,m≦100000,1≦ai,x≦10000のすべての操作が終了した後、1≦ai≦10000を保証する.
テーマ分析
何か見つけた
テーマを分析し、条件を観察する.すべての操作後、a配列の各数は10000以下の正の整数であり、初期値も10000以下の正の整数であり、加算された数は0より大きいことが保証される.これは何を説明していますか.操作が終了するたびにaiは10000以下である.我々は組合せ数の知識から,10000以内のS集合の数を30個(=24+23+22+2)個と算出し,この総数をkとする.
ブロック大法
ブロック分けがいい!ブロック分けがいい!ブロック分けがいい!(重要なことは3回)ブロック分割アルゴリズムを考慮し、各ブロックサイズをbとし、ブロック内で各数の出現回数を配列tで維持する.修正操作を実行すると、ブロック外の数に対して、ブロック全体を直接再構成することができ、時間複雑度はO(b)である.連続したブロックについては,時間複雑度O(nb)のブロック上のタグに修正値を加えることができる.クエリー操作を実行する場合:ブロック外の数に対して、ブロック全体を直接再構築し、暴力統計、時間複雑度O(b)を行うことができます.連続するブロックについて、あるブロックを+としてマークするΔx,Σi∈Sti−を統計することができるΔx,時間複雑度はO(nkb)であった.そして,全時間複雑度はO(m(b+nkb))であり,b=nk−−−√のとき,時間複雑度はO(mnk−−−√)が最適であった.
コード実装

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

const int B=1800;
const int A=10000;
const int K=30;
const int N=100000;

bool iss[A+1];
int a[N+1];
int s[K+1];
int n,m,b,cnt;

struct block
{
    int l,r,mark;
    int bin[A+1];

    inline void rebuild()
    {
        if (!mark)
            return;
        for (int i=l;i<=r;i++)
            bin[a[i]]--;
        for (int i=l;i<=r;i++)
        {
            a[i]+=mark;
            bin[a[i]]++;
        }
        mark=0;
    }

    inline int query(int st,int en)
    {
        rebuild();
        int ret=0;
        for (int i=st;i<=en;i++)
            ret+=iss[a[i]];
        return ret;
    }

    inline void change(int st,int en,int edit)
    {
        rebuild();
        int ret=0;
        for (int i=st;i<=en;i++)
        {
            bin[a[i]]--;
            a[i]+=edit;
            bin[a[i]]++;
        }
    }
}bs[B+1];

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9')
    {
        if (ch=='-')
            f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline bool check(int x)
{
    while (x)
    {
        if (x%10!=4&&x%10!=7)
            return false;
        x/=10;
    }
    return true;
}

inline void preparation()
{
    for (int i=1;i<=A;i++)
        if (check(i))
        {
            iss[i]=true;
            s[++s[0]]=i;
        }
}

int main()
{
    preparation();
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    n=read(),m=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    b=floor(sqrt(n*K))+1;
    cnt=n/b;
    for (int i=1;i<=cnt;i++)
    {
        bs[i].l=(i-1)*b+1;
        bs[i].r=i*b;
        for (int j=bs[i].l;j<=bs[i].r;j++)
            bs[i].bin[a[j]]++;
    }
    if (n%b)
    {
        cnt++;
        bs[cnt].l=(cnt-1)*b+1;
        bs[cnt].r=n;
        for (int j=bs[cnt].l;j<=bs[cnt].r;j++)
            bs[cnt].bin[a[j]]++;
    }
    char oprt;
    int l,r,x;
    while (m--)
    {
        oprt=getchar();
        while (oprt!='a'&&oprt!='c')
            oprt=getchar();
        l=read(),r=read();
        if (oprt=='a')
        {
            x=read();
            int lt=(l-1)/b+1,rt=(r-1)/b+1;
            if (lt==rt)
            {
                bs[lt].change(l,r,x);
                continue;
            }
            if (l!=bs[lt].l)
            {
                bs[lt].change(l,bs[lt].r,x);
                lt++;
            }
            if (r!=bs[rt].r)
            {
                bs[rt].change(bs[rt].l,r,x);
                rt--;
            }
            for (int i=lt;i<=rt;i++)
                bs[i].mark+=x;
        }
        else
        {
            int lt=(l-1)/b+1,rt=(r-1)/b+1;
            if (lt==rt)
            {
                printf("%d
",bs[lt].query(l,r));
                continue;
            }
            int ans=0;
            if (l!=bs[lt].l)
            {
                ans+=bs[lt].query(l,bs[lt].r);
                lt++;
            }
            if (r!=bs[rt].r)
            {
                ans+=bs[rt].query(bs[rt].l,r);
                rt--;
            }
            for (int i=lt;i<=rt;i++)
                for (int j=1;j<=K;j++)
                    if (s[j]>=bs[i].mark)
                        ans+=bs[i].bin[s[j]-bs[i].mark];
            printf("%d
",ans);
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}