比赛 |
树形数据结构进阶(再进阶) |
评测结果 |
AAAAAAAAAAAAAAAAAAAAA |
题目名称 |
幸运数列 |
最终得分 |
100 |
用户昵称 |
李奇文 |
运行时间 |
9.645 s |
代码语言 |
C++ |
内存使用 |
4.02 MiB |
提交时间 |
2025-04-19 10:40:19 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
/*int n,m;
int a[N];
struct tree{
int l,r,w,tb,lazy;
}f[N*4];
bool check(int x){
int d=x%10;
while(x){
if(d!=4||d!=7) return 0;
x=x/10;
d=x%10;
}
return 1;
}
void build(int p,int l,int r) {
f[p].l=l,f[p].r=r;
if(l==r) {
if(check(a[l])) f[p].tb=1;
else f[p].tb=0;
f[p].w=a[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
f[p].w=f[p*2].w+f[p*2+1].w;
f[p].tb=f[p<<1].tb+f[p<<1|1].tb;
return;
}
void pushlazy(int p){
if(!f[p].lazy){
return;
}else{
int lp=p*2,rp=p*2+1;
f[lp].lazy+=f[p].lazy;
f[rp].lazy+=f[p].lazy;
int mid=(f[p].l+f[p].r)>>1;
f[lp].w+=f[p].lazy;
f[rp].w+=f[p].lazy;
f[p].lazy=0;
}
return;
}
void change(int p,int l,int r,int k){
if(l<=f[p].l&&f[p].r<=r){
f[p].lazy+=k;
f[p].w+=(f[p].r-f[p].l+1)*k;
return;
}else{
pushlazy(p);
int mid=(f[p].l+f[p].r)/2;
if(l<=mid) change(p*2,l,r,k);
if(mid<r) change(p*2+1,l,r,k);
f[p].w=f[p*2].w+f[p*2+1].w;
}
return;
}
void pushdown(int p) {
if(f[p].l==f[p].r){
if(check(f[p].w)) f[p].tb=1;
else f[p].tb=0;
return;
}
pushlazy(p);
int mid=(f[p].l+f[p].r)/2;
pushdown(p*2);
pushdown(p*2+1);
f[p].tb=f[p<<1].tb+f[p<<1|1].tb;
}
int query(int p,int x,int y) {
if(x<=f[p].l&&f[p].r<=y) {
return f[p].tb;
}
pushlazy(p);
int mid=(f[p].l+f[p].r)/2,sum=0;
if(x<=mid) {
sum+=query(p*2,x,y);
}
if(mid<y) {
sum+=query(p*2+1,x,y);
}
return sum;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
while(m--){
string s;
int l,r,op=0;
scanf("%s%d%d",&s,&l,&r);
if(s=="count"){
if(op) pushdown(1);
printf("%d\n",query(1,l,r));
}else{
int k;
op++;
scanf("%d",&k);
change(1,l,r,k);
}
}
return 0;
}*/
bool g[10001];
int f[30]={4,7,44,77,47,74,444,447,474,744,477,774,747,777,4444,4447,4474,4744,7444,4477,4747,7447,7474,7744,4774,7774,7747,7477,4777,7777};
void init(){
for(int i=0;i<=29;i++){
g[f[i]]=true;
}
}
int a[N],c[N],n,m;
int lowbit(int x){
return x&(-x);
}
void add(int x,int k){
while(x<=n){
c[x]+=k;
x+=lowbit(x);
}
}
int count(int x){
int ans=0;
while(x>0){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
int main(){
freopen("cf121e.in","r",stdin);
freopen("cf121e.out","w",stdout);
init();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(g[a[i]]){
add(i,1);
}
}
while(m--){
string s;
int l,r;
std::cin>>s>>l>>r;
if(s=="count"){
printf("%d\n",count(r)-count(l-1));
}else{
int k;
scanf("%d",&k);
for(int i=l;i<=r;i++){
if(g[a[i]]) add(i,-1);
a[i]+=k;
if(g[a[i]]) add(i,1);
}
}
}
return 0;
}