codeforces 121E Lucky Array

codeforces 121E Lucky Array

​​ Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya has an array consisting of n numbers. He wants to perform m operations of two types:

add l r d — add an integer d to all elements whose indexes belong to the interval from l to r, inclusive (1 ≤ l ≤ r ≤ n, 1 ≤ d ≤ 104); count l r — find and print on the screen how many lucky numbers there are among elements with indexes that belong to the interval from l to r inclusive (1 ≤ l ≤ r ≤ n). Each lucky number should be counted as many times as it appears in the interval. Petya has a list of all operations. The operations are such that after all additions the array won’t have numbers that would exceed 104. Help Petya write a program that would perform these operations.

Input The first line contains two integers n and m (1 ≤ n, m ≤ 105) — the number of numbers in the array and the number of operations correspondingly. The second line contains n positive integers, none of which exceeds 104 — those are the array numbers. Next m lines contain operations, one per line. They correspond to the description given in the statement.

It is guaranteed that after all operations are fulfilled each number in the array will not exceed 104.

Output For each operation of the second type print the single number on the single line — the number of lucky numbers in the corresponding interval.

Examples Input 3 6 2 3 4 count 1 3 count 1 2 add 1 3 2 count 1 3 add 2 3 3 count 1 3 Output 1 0 1 1 Input 4 5 4 4 4 4 count 1 4 add 1 4 3 count 1 4 add 2 3 40 count 1 4 Output 4 4 4 Note In the first sample after the first addition the array will look in the following manner:

4 5 6

After the second addition:

4 8 9

The second sample after the first addition:

7 7 7 7

After the second addition:

7 47 47 7

题意 要求我们求一段区间内 幸运数字有多少个 对于幸运数字的定义是：只能包含十进制下的4&7而且题目保证这个他加的数最终不会超过1e4那么我们考虑这题是否和有一个开根号的那题相似呢 大概leoly说很像呢 所以做法就是 我对于线段树上每个点我去储存d[i]表示我的值到距离我最近的那个幸运数字的差是多少 然后维护一个这些值的最小值 维护一下这个最小值最早出现在哪里 再维护一下我最小值一共有几个 然后修改的时候我相当于是区间减法 然后如果这个整个所有1~n中出现了负数 那么我就定位到第一个负数出现在哪里把他改成距离下一个幸运数字的大小 然后重新更新上去 最后直到我1~n中不再有<0的数出现即可 询问的时候只需要询问我最小值为0的数有多少个即可

#include #include#include#define N 110000#define inf 0x3f3f3f3f#define pa pairusing namespace std;inline int read(){ int x=0;char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}struct node{ int left,right,min,mp,mn,v,lazy;}tree[N<<2];int mp[]={0,4,7,44,47,74,77,444,447,474,744,477,747,774,777,4444,4447,4474,4744,7444,4477,4747,7447,4774,7474,7744,4777,7477,7747,7774,7777,999999999};int n,m,a[N],num,root;char s[30];inline void update(int x){ int l=tree[x].left,r=tree[x].right; if (tree[l].min==tree[r].min){ tree[x].mn=tree[l].mn+tree[r].mn; tree[x].min=tree[l].min;tree[x].mp=min(tree[l].mp,tree[r].mp); } if (tree[l].min>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);update(x);}inline void change(int x,int l,int r,int p){ if(l==r){ int now=tree[x].v-tree[x].min,pos=lower_bound(mp+1,mp+32,now)-mp; tree[x].v=mp[pos];tree[x].min=mp[pos]-now;return; } int mid=l+r>>1;pushdown(x); if(p<=mid) change(tree[x].left,l,mid,p);else change(tree[x].right,mid+1,r,p);update(x);}inline pa update1(pa p1,pa p2){ int fi,se; if(p1.firstp2.first) fi=p2.first,se=p2.second;return make_pair(fi,se);}inline pa qr(int x,int l,int r,int l1,int r1){ if(l1<=l&&r1>=r){pa pp;pp=make_pair(tree[x].min,tree[x].mn);return pp;} int mid=l+r>>1;pa tmp;tmp=make_pair(inf,99);pushdown(x); if(l1<=mid) tmp=update1(tmp,qr(tree[x].left,l,mid,l1,r1)); if(r1>mid) tmp=update1(tmp,qr(tree[x].right,mid+1,r,l1,r1));return tmp;}inline void insert1(int x,int l,int r,int l1,int r1,int v){ if(l1<=l&&r1>=r){tree[x].lazy+=v;tree[x].min-=v;return;} int mid=l+r>>1;pushdown(x); if(l1<=mid) insert1(tree[x].left,l,mid,l1,r1,v); if(r1>mid) insert1(tree[x].right,mid+1,r,l1,r1,v);update(x);}int main(){ freopen("cf.in","r",stdin); n=read();m=read();sort(mp+1,mp+32); //for (int i=1;i<=31;++i) printf("%d\n",mp[i]); for (int i=1;i<=n;++i) a[i]=read();build(root,1,n); for (int i=1;i<=m;++i){ scanf("%s",s+1);if (s[1]=='c'){ int l=read(),r=read();pa pp=qr(root,1,n,l,r); if(pp.first==0) printf("%d\n",pp.second);else printf("0\n"); } else{ int l=read(),r=read(),v=read();insert1(root,1,n,l,r,v); while(tree[root].min<0) change(root,1,n,tree[root].mp); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。