1922. [CF 121E]幸运数列★★★ 输入文件：cf121e.in 输出文件：cf121e.out 简单对比时间限制：3 s 内存限制：256 MB
【题目描述】
对于欧洲人来说，“幸运数”是指那些十进制只由4或7组成的数。财务员Petya需要维护一个支持如下操作的整数数列： add l r d — 表示将[l, r]区间内的所有数加上一个正整数d（）。 count l r — 统计[l, r]区间内有多少个“幸运数”。() 请你帮助Petya实现它。
【输入格式】
第一行有两个正整数n, m ，表示数组的长度和操作的个数。 第二行有n个不大于的正整数，表示这个初始数列。 接下来有m行，每行表示一个操作。 输入保证过程中数组中所有元素始终为不超过的正整数.
【输出格式】
输出若干行。对于所有的count l r 操作，按顺序给出每个询问的答案。
【样例输入1】
3 62 3 4count 1 3count 1 2add 1 3 2count 1 3add 2 3 3count 1 3
【样例输出1】
1011
【样例输入2】
4 54 4 4 4count 1 4add 1 4 3count 1 4add 2 3 40count 1 4
【样例输出2】
444
题解：
直接暴力，时间充裕。 因为满足要求的数不超过30个，直接打表即可，然后暴力修改即可。 实践证明，树状数组在区间求和方面的确优于线段树。
Code：
线段树：
;int n,m,ans,a[N],tree[N<<2],b[50]={0,4,7,44,47,74,77,444,447,474,477,744,747,774,777,4444,4447,4474,4477,4744,4747,4774,4777,7444,7447,7474,7477,7744,7747,7774,7777,};bool f[10010]; char ch[10];inline int in(){int x=0; char ch=getchar();while (ch<‘0′ || ch>’9′) ch=getchar();while (ch>=’0′ && ch<=’9’) x=x*10+ch-‘0′,ch=getchar();return x;}inline void push_up(int rt){tree[rt]=tree[rt<<1]+tree[rt<<1|1];}inline void add(int rt,int l,int r,int x,int k){if (l==r){tree[rt]+=k;return;}int mid=(l+r)>>1;if (x<=mid) add(lchild,x,k);else add(rchild,x,k);push_up(rt);}inline int query(int rt,int l,int r,int ll,int rr){if (ll<=l && r<=rr) return tree[rt];int mid=(l+r)>>1,k=0;if (ll<=mid) k+=query(lchild,ll,rr);if (rr>mid) k+=query(rchild,ll,rr);return k;}int main(){n=in(),m=in();for (int i=1; i<=30; i++) f[b[i]]=1;for (int i=1; i<=n; i++){a[i]=in();if (f[a[i]]) add(root,i,1);}while (m–){scanf(“%s”,&ch);int x=in(),y=in(),z;if (ch[0]==’a’){z=in();for (int i=x; i<=y; i++){int k=0;if (f[a[i]]) k–;a[i]+=z;if (f[a[i]]) k++;if (k) add(root,i,k);}}else printf(“%d\n”,query(root,x,y));}return 0;}
树状数组：
;int n,m,ans,a[N],c[N],b[50]={0,4,7,44,47,74,77,444,447,474,477,744,747,774,777,4444,4447,4474,4477,4744,4747,4774,4777,7444,7447,7474,7477,7744,7747,7774,7777,};bool f[10010]; char ch[10];inline int in(){int x=0; char ch=getchar();while (ch<‘0′ || ch>’9′) ch=getchar();while (ch>=’0′ && ch<=’9’) x=x*10+ch-‘0′,ch=getchar();return x;}inline void add(int x,int k){for (int i=x; i<=n; i+=lowbit(i)) c[i]+=k;}inline int query(int x){int s=0;for (int i=x; i>0; i-=lowbit(i)) s+=c[i];return s;}int main(){n=in(),m=in();for (int i=1; i<=30; i++) f[b[i]]=1;for (int i=1; i<=n; i++){a[i]=in();if (f[a[i]]) add(i,1);}while (m–){scanf(“%s”,&ch);int x=in(),y=in(),z;if (ch[0]==’a’){z=in();for (int i=x; i<=y; i++){int k=0;if (f[a[i]]) k–;a[i]+=z;if (f[a[i]]) k++;if (k) add(i,k);}}else printf(“%d\n”,query(y)-query(x-1));}return 0;}
，每一天都是一个阶梯，是向既定目标迈进的新的一步。
