比赛 树形数据结构进阶(再进阶) 评测结果 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;
}