比赛 |
树形数据结构进阶(再进阶) |
评测结果 |
AAAAAAAAATTATTATTATTT |
题目名称 |
幸运数列 |
最终得分 |
57 |
用户昵称 |
duck |
运行时间 |
55.787 s |
代码语言 |
C++ |
内存使用 |
4.31 MiB |
提交时间 |
2025-04-19 11:32:35 |
显示代码纯文本
#include<bits/stdc++.h>
#define mid ((l+r)>>1)
#define N 100086
using namespace std;
map<int ,int>ga;
int n,m,du1,du2,du3,B;
int a[N],sum[N],pos[N],l[N],r[N];
string op;
int ask(int l1,int r1){
int ans=0;
if(pos[l1]==pos[r1]){for(int i=du1;i<=du2;i++) ans+=ga[a[i]];return ans;}
for(int i=du1;i<=r[pos[du1]];i++) ans+=ga[a[i]];
for(int i=pos[du1]+1;i<=pos[du2]-1;i++) ans+=sum[i];
for(int i=l[pos[du2]];i<=du2;i++) ans+=ga[a[i]];
return ans;
}
signed main(){
freopen("cf121e.in","r",stdin);
freopen("cf121e.out","w",stdout);
memset(l,0x3f,sizeof l);ga[4]=1,ga[7]=1,ga[44]=1,ga[74]=1,ga[47]=1,ga[77]=1,ga[444]=1,ga[474]=1,ga[447]=1,ga[477]=1,ga[744]=1,ga[774]=1,ga[747]=1,ga[777]=1,ga[4444]=1,ga[4474]=1,ga[4447]=1,ga[4477]=1,ga[4744]=1,ga[4774]=1,ga[4747]=1,ga[4777]=1,ga[7444]=1,ga[7474]=1,ga[7447]=1,ga[7477]=1,ga[7744]=1,ga[7774]=1,ga[7747]=1,ga[7777]=1;
scanf("%d%d",&n,&m);
B=sqrt(n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
pos[i]=i/B+1;
sum[pos[i]]+=ga[a[i]];
l[pos[i]]=min(l[pos[i]],i);
r[pos[i]]=max(r[pos[i]],i);
}
for(int i=1;i<=m;i++){
cin>>op;
if(op[0]=='a'){
scanf("%d%d%d",&du1,&du2,&du3);
for(int i=du1;i<=du2;i++){
sum[pos[i]]-=ga[a[i]];
a[i]+=du3;
sum[pos[i]]+=ga[a[i]];
}
}
else{
scanf("%d%d",&du1,&du2);
cout<<ask(du1,du2)<<endl;
}
}
return 0;
}