题目大意
维护一个序列，支持以下操作：
-
区间加一个大于 \(0\) 的数。
-
区间查询有多少个数位上只包含 \(4\) 或 \(7\) 的数。
思路分析
看起来很不可做，但考虑到题目给了一个特殊性质：
保证所有数操作前后都不超过 \(10^4\)。
那么如果暴力进行区间加，最坏情况会加 \(10^9\) 次，考虑到 \(4\text{s}\) 的时限，复杂度是正确的。
区间查询的话，容易发现 \(10^4\) 范围内满足条件的数只有 \(30\) 个，打一个表出来就行了。
再随便套一个数据结构用来求和就可以了。
时间复杂度为 \(O(nV+f(n))\)，其中 \(f(n)\) 为用于求和的数据结构的时间复杂度。
代码
线段树被不知道为什么卡常了，因此这里写的是分块。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100100;
#define mid ((l+r)>>1)
int num[]={4,7,44,47,77,74,444,447,477,474,744,747,774,777,4444,4447,4474,4477,4744,4747,4774,4777,7444,7447,7474,7477,7744,7747,7774,7777};
//表不要打错了
int n,m,in1,in2,in3,B;
int vis[N],inp[N],sum[N],pos[N],L[N],R[N];
char op[7];
int ask(int l,int r){
int res=0;
if(pos[l]==pos[r]){for(int i=in1;i<=in2;i++) res+=vis[inp[i]];return res;}
for(int i=in1;i<=R[pos[in1]];i++) res+=vis[inp[i]];
for(int i=pos[in1]+1;i<=pos[in2]-1;i++) res+=sum[i];
for(int i=L[pos[in2]];i<=in2;i++) res+=vis[inp[i]];
return res;
}
int main(){
memset(L,0x3f,sizeof L);
for(int i=0;i<30;i++) vis[num[i]]=1;
scanf("%d%d",&n,&m);
B=sqrt(n);
for(int i=1;i<=n;i++){
scanf("%d",&inp[i]);
pos[i]=i/B+1;
sum[pos[i]]+=vis[inp[i]];
L[pos[i]]=min(L[pos[i]],i);
R[pos[i]]=max(R[pos[i]],i);
}
while(m--){
scanf("%s",op+1);
if(op[1]=='a'){
scanf("%d%d%d",&in1,&in2,&in3);
for(int i=in1;i<=in2;i++){
sum[pos[i]]-=vis[inp[i]];
inp[i]+=in3;
sum[pos[i]]+=vis[inp[i]];
//对于每个数暴力加
}
}
if(op[1]=='c'){
scanf("%d%d",&in1,&in2);
cout<<ask(in1,in2)<<'\n';//区间查询
}
}
return 0;
}