题解 CF121E 【Lucky Array】

· · 题解

题解-CF121E Lucky Array

就是有两种操作：

add:[l,r],x$把$[l,r]$区间里面的数加上$x * $Solution

由于ai最大值很小，直接O(lim)预处理即可

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

对于修改操作我们可以暴力O(n)扫一遍对于原来是幸运数的数先add(i,-1)再add(i,1)如果原数加上val后为幸运数。

时间复杂度：O(M*logN)

#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;
}