题解-CF121E Lucky Array

• 题目大意

就是有两种操作：

把区间里面的数加上

询问区间里有多少幸运数字

由于最大值很小，直接预处理即可

然后用树状数组维护区间这种数的个数。对于查询操作我们直接输出即可。

对于修改操作我们可以暴力扫一遍对于原来是幸运数的数先再如果原数加上后为幸运数。

时间复杂度：

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;

const int maxn=200005;

int n,m,c[maxn],a[maxn],is[maxn],ans,ma;

inline void init(int x) {
    for ( int i=1;i<=x;i++ ) {
        int tmp=i;
        int ok=1;
        while(tmp) {
            int p=tmp%10;
            if(p!=4&&p!=7) {
                ok=0;
                break;
            }
            tmp/=10;
        }
        if(ok) is[i]=1;
    }
}

inline void add(int x,int val) {
    while(x<=n) {
        c[x]+=val;
        x+=lowbit(x);
    }
}

inline int query(int x) {
    int ret=0;
    while(x) {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}

inline int read() {
    int sum=0; char ch=getchar();
    while(!isdigit(ch)) 
        ch=getchar();
    while(isdigit(ch)) 
        sum=sum*10+(ch^48),ch=getchar();
    return sum;
}

int main() {
    n=read();
    m=read();
    init(200001);
    for ( int i=1;i<=n;i++ ) {
        a[i]=read();
        if(is[a[i]]) add(i,1);
    }
    char type[11];
    for ( int i=1;i<=m;i++ ) {
        scanf("%s",type+1);
        if(type[1]==99) {
            int l=read();
            int r=read();
            printf("%d\n",query(r)-query(l-1));
        }
        else {
            int l=read();
            int r=read();
            int val=read();
            if(!val) continue;
            for ( int j=l;j<=r;j++ ) {
                if(is[a[j]]) add(j,-1);
                a[j]+=val;
                if(is[a[j]]) add(j,1);
            }
        }
    }
    return 0;
}